글 읽기 - 세그먼트 트리에 뭐가 문제일까요?

hs2seo 6년 전 0

세그먼트 트리로 구현했는데 33%에서 에러가 나네요

뭐가 잘 못 된건가요?

import java.util.Scanner;

public class Main {

	static int T;
	static int N;
	static int M;

	static int[] pos;
	static int[] nums;
	static int[] tree;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();

		while (T-- > 0) {
			N = sc.nextInt();
			M = sc.nextInt();
			int K = N + M;

			pos = new int[N + 1];
			nums = new int[K];
			for (int i = 1; i <= N; i++) {
				pos[i] = i + M - 1;
				nums[i + M - 1] = 1;
			}

			int treeHeight = (int) Math.ceil(Math.log(K) / Math.log(2));
			int treeSize = (int) (Math.pow(2, treeHeight + 1));

			tree = new int[treeSize];
			init(1, 0, K - 1);

			while (M-- > 0) {
				int movie = sc.nextInt();
				int current = pos[movie];

				int ans = query(1, 0, K - 1, 0, current);
				System.out.printf("%d ", ans - 1);

				if (ans != 1) {
					update(1, 0, K - 1, current, -1);
					pos[movie] -= ans;
					update(1, 0, K - 1, pos[movie], 1);
				}

			}

			System.out.println();
		}

		sc.close();
	}

	public static void init(int node, int start, int end) {

		if (start == end) {
			tree[node] = nums[start];
		} else {
			int half = (start + end) / 2;
			init(node * 2, start, half);
			init(node * 2 + 1, half + 1, end);

			tree[node] = tree[node * 2] + tree[node * 2 + 1];
		}
	}

	public static void update(int node, int start, int end, int index, int diff) {

		if (!(start <= index && index <= end))
			return;

		tree[node] += diff;

		if (start != end) {
			int half = (start + end) / 2;
			update(node * 2, start, half, index, diff);
			update(node * 2 + 1, half + 1, end, index, diff);
		}
	}

	public static int query(int node, int start, int end, int i, int j) {

		if (i > end || j < start)
			return -1;

		if (i <= start && end <= j)
			return tree[node];

		int half = (start + end) / 2;
		int m1 = query(node * 2, start, half, i, j);
		int m2 = query(node * 2 + 1, half + 1, end, i, j);

		if (m1 == -1)
			return m2;
		else if (m2 == -1)
			return m1;
		else
			return m1 + m2;

	}
}

sgchoi5 6년 전 0

nwerc 문제는 대회에서 사용했었던 TC 가 공개되어 있으니 한 번 써보세요...

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

세그먼트 트리에 뭐가 문제일까요?

hs2seo 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말