글 읽기 - 세그먼트 트리로 풀었는데 도저히 왜틀렸는지 이해가안되요 ㅠ

tkt921 4년 전 0

안녕하세요

세그먼트 트리 2개 사용해서 문제 풀었는데, 제가 만든 모든 테스트케이스에서는 올바른 정답이 출력되는데요

제출만하면 틀렸다고 나오네요...

도움좀 받을수 있을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st;
	public static int n,k,v;
	public static int max[];
	public static int min[];
	public static int map[];
	public static long max_count, min_count,start,length;
	
	public static void main(String args[]) throws IOException {
		st = new StringTokenizer(br.readLine());
		n  = Integer.parseInt(st.nextToken());
		k  = Integer.parseInt(st.nextToken());
		
		max = new int[1048576];
		min = new int[1048576];
		map = new int[n+1];
		start= 1048576/2;
		length = 1048576;
		for(int i=1;i<1048576;i++) {
			max[i] = -1;
			min[i] = 65537;
		}
		
		max_count = 0;
		min_count = 0;
		
		for(int i=1;i<=k;i++) {
			st = new StringTokenizer(br.readLine());
			v  = Integer.parseInt(st.nextToken());
			long temp = start+i-1;
			max[(int) temp] = v;
			map[i] = v;
			while(temp>1) {
				temp = temp/2;
				max[(int) temp] = Math.max(max[(int) (temp*2)], max[(int) (temp*2+1)]);
			}
			max_count++;			
		}
		
		long value = 0;
		long median =  0;
		for(int i=k;i<=n;i++) {
			
			if(k%2==1) {
				while(max_count>min_count+1) {
					// max to min
					int max_v = max[1];
					int point = find(max_v,max);
					move_max_to_min(point, max_v);
				}
				
				while(max_count<min_count) {
					//min to max
					int min_v = min[1];
					int point = find(min_v,min);
					move_min_to_max(point,min_v);
				}
			}
			else {
				while(max_count>=min_count+1) {
					// max to min
					int max_v = max[1];
					int point = find(max_v,max);
					move_max_to_min(point, max_v);
				}
				
				while(max_count<min_count) {
					//min to max
					int min_v = min[1];
					int point = find(min_v,min);
					move_min_to_max(point,min_v);
				}
			}
			
			median = max[1];
			value = value+median;
			
			if(i==n) {
				break;
			}
			st = new StringTokenizer(br.readLine());
			v  = Integer.parseInt(st.nextToken());
			
			// 이전꺼 뺴기
			
			int p = (int) (start+i);
			int asis = p-k;
					
			if(max[asis]>=0) {
				max[asis] = -1;
				max_count--;
				
				int before = asis;
				while(before>1) {
					before = before/2;
					max[before] = Math.max(max[before*2],max[before*2+1]);
				}
			}else if(min[asis]<65337) {
				min[asis] = 65537;
				min_count--;
				int before = asis;
				while(before>1) {
					before = before/2;
					min[before] = Math.min(min[before*2],min[before*2+1]);
				}
			}
			
			
			if(v>median) {
				update_min(p,v);
			}else {
				update_max(p,v);
			}
		}
		System.out.println(value);
	
	}

	private static void update_max(int p, int v) {
		max[p] = v;
		
		while(p>1) {
			p=p/2;
			max[p] = Math.max(max[p*2], max[p*2+1]);
		}
		max_count++;
	}
	private static void update_min(int p, int v) {
		min[p] = v;
		
		while(p>1) {
			p=p/2;
			min[p] = Math.min(min[p*2], min[p*2+1]);
		}
		min_count++;
	}
	private static void move_min_to_max(int point, int v) {
		max[point] = v;
		min[point] = 65537;
		
		int p = point;
		while(p>1) {
			p=p/2;
			max[p] = Math.max(max[p*2],max[p*2+1]);
			min[p] = Math.min(min[p*2],min[p*2+1]);
		}
		max_count++;
		min_count--;
	}

	private static void move_max_to_min(int point, int v) {
		
		max[point] = -1;
		min[point] = v;
		
		int p = point;
		while(p>1) {
			p=p/2;
			max[p] = Math.max(max[p*2],max[p*2+1]);
			min[p] = Math.min(min[p*2],min[p*2+1]);
		}
		max_count--;
		min_count++;
		
	}

	private static int find(int v, int[] data) {
		int p=1;
		while(length>p) {
			if(p*2>=length) {
				break;
			}
			if(v==data[p*2+1] && v!=data[p*2]) {
				p = p*2+1;
			}else {
				p = p*2;
			}
		}
		return p;
	}

}

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

문제

문제

출처

ICPC

세그먼트 트리로 풀었는데 도저히 왜틀렸는지 이해가안되요 ㅠ

tkt921 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말