글 읽기 - 왜틀리는지 모르겠습니다 ㅠㅠ 반례 있을까요?

jjj704 2년 전 0

인덱스트리로 풀었습니다.

예제도 맞고 직접 데이터 만들어서 돌려봐도 맞는데

제출시 틀리네요 ㅠㅠ 반례가 뭐가 있을까요?

도움 부탁드립니다.

트리 크기는 참고로 아래와 같이 지정했습니다.

private static void initTree() {

leafCount = 1;

while (leafCount < N) {

leafCount *= 2;

}

minTree = new int[leafCount * 2];

maxTree = new int[leafCount * 2];

}

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, leafCount;
	static int[] minTree, maxTree;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		initTree();
		Arrays.fill(minTree, Integer.MAX_VALUE);
		for (int i = 0; i < N; i++) {
			int idx = leafCount + i;
			int num = Integer.parseInt(br.readLine());
			minTree[idx] = num;
			maxTree[idx] = num;
			while (idx > 1) {
				minTree[idx / 2] = Math.min(minTree[idx / 2], minTree[idx]);
				maxTree[idx / 2] = Math.max(maxTree[idx / 2], maxTree[idx]);
				idx /= 2;
			}
		}
//		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s_idx = Integer.parseInt(st.nextToken()) + leafCount - 1;
			int e_idx = Integer.parseInt(st.nextToken()) + leafCount - 1;
//			sb.append(find(0, s_idx, e_idx, minTree) + " " + find(1, s_idx, e_idx, maxTree) + "\n");
			System.out.println(find(0, s_idx, e_idx, minTree) + " " + find(1, s_idx, e_idx, maxTree));
		}
//		System.out.println(sb);
	}

	private static int find(int flag, int s_idx, int e_idx, int[] tree) {
		// flag가 0이면 최소값, 1이면 최대값
		int num1, num2;
		if (flag == 0) {
			num1 = Integer.MAX_VALUE;
			num2 = Integer.MAX_VALUE;
		} else {
			num1 = 0;
			num2 = 0;
		}

		while (s_idx < e_idx) {
			if (s_idx % 2 == 1) {
				num1 = tree[s_idx];
				s_idx++;
			}
			if (e_idx % 2 == 0) {
				num2 = tree[e_idx];
				e_idx--;
			}
			s_idx /= 2;
			e_idx /= 2;
		}
		int value = 0;
		if (s_idx == e_idx) {
			if (flag == 0) {
				value = Math.min(Math.min(num1, num2), tree[s_idx]);
			} else {
				value = Math.max(Math.max(num1, num2), tree[s_idx]);
			}
		} else {
			if (flag == 0) {
				value = Math.min(num1, num2);
			} else {
				value = Math.max(num1, num2);
			}
		}
		return value;
	}

	private static void initTree() {
		leafCount = 1;
		while (leafCount < N) {
			leafCount *= 2;
		}
		minTree = new int[leafCount * 2];
		maxTree = new int[leafCount * 2];
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜틀리는지 모르겠습니다 ㅠㅠ 반례 있을까요?

jjj704 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말