글 읽기 - 11658 예제는 맞았는데, 실제로는 틀리네요. 어느부분이 잘못됬을까요?

tkt921 4년 전 0

트리 사용해서, 각 행별로 부분합 구했는데요

예제는 다 맞아서 제출했는데, 제출시 실패했습니다가 뜨는데, 어디가 잘못된건지 모르겠습니다.

반례라도 찾을수 있을까요?

도움 부탁드립니다.

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

public class p_11658 {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st;
	public static int n,m;
	public static int w, x1, y1, x2, y2;
	public static int x,y,c;
	public static long map[][];
	public static void main(String args[]) throws IOException {
		
		
		st = new StringTokenizer(br.readLine());
		n  = Integer.parseInt(st.nextToken());
		m  = Integer.parseInt(st.nextToken());

		int cnt = 1;
		while(cnt<n) {
			cnt = cnt * 2;
		}
		
		cnt = cnt*2;
		
		int start = cnt/2;
		int end  = cnt;
		map = new long[n+1][cnt];
		int num = start;
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=n;j++) {
				map[i][start+j-1] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1;i<=n;i++) {
			start = cnt/2;
			end   = cnt;
			while(start > 1) {
				for(int j=start;j<end;j=j+2) {
					map[i][j/2] = map[i][j] + map[i][j+1];
				}
				start = start/2;
				end = end/2;
			}
		}
		
		for(int i=1;i<=m;i++) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			if(w == 1) {
				 x1 = Integer.parseInt(st.nextToken());
				 y1 = Integer.parseInt(st.nextToken());
				 x2 = Integer.parseInt(st.nextToken());
				 y2 = Integer.parseInt(st.nextToken());
				 
				 start = cnt/2 + y1 -1;
				 end   = cnt/2 + y2 -1;
				 
				 long hap = 0;
				 for(int j=x1;j<=x2;j++) {
					 long value = find(map[j],start, end);
					 hap = value + hap;
				 }
				 System.out.println(hap);
			}else {
				x = Integer.parseInt(st.nextToken()); 
				y = Integer.parseInt(st.nextToken()); 
				c = Integer.parseInt(st.nextToken()); 
				
				int point = cnt/2 + y -1;
				map[x][point] = c;
				
				start = cnt/2;
				end   = cnt;
				while(start > 1) {
					for(int j=start;j<end;j=j+2) {
						map[x][j/2] = map[x][j] + map[x][j+1];
					}
					start = start/2;
					end = end/2;
				}
			}
		}		
	}
	private static long find(long[] data, int left, int right) {
		
		long value = 0;
		if(left == right) {
			value = data[left];
		} else {
			while(left<right) {
				
				if(left%2==1) {
					value = data[left] + value;
					left = left + 1;
				}
				if(right%2==0) {
					value = data[right] + value;
					right = right-1;
					
				}
				left = left/2;
				right = right/2;
				
				if(left!=right) {
					value = data[left]+value;
					value = data[right]+value;
				}else {
					value = data[left]+value;
				}
				left++;
				right--;
				
			}
		}
		return value;
	}
}

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

문제

문제

출처

ICPC

11658 예제는 맞았는데, 실제로는 틀리네요. 어느부분이 잘못됬을까요?

tkt921 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말