글 읽기 - 구간 곱 오류 좀 찾아주세요~~~

kenocis9 6년 전 0

시간초과 문제를 해결하려고 for 문에서 i--를 i/=2로 변경했더니 그때부터 계속 틀렸다고 나오는데 어디가 잘못되었는지 모르겠습니다.

도와주세요..

for(int i = p; i >= 1; i/=2){
     if(c == 0){
      tree[i] = 0;
     }else{
      tree[i] = tree[i*2] * tree[i*2+1];
     }
    }

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Baekjoon_11505_segment {
	
	static long[] tree;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int NN;	//	트리의 말단 노드갯수
		
		for(NN = 1; NN < N; NN*=2);
		
		tree = new long[NN*2];
		
		for(int i = NN; i < NN+N; i++){
			tree[i] = Integer.parseInt(br.readLine());
		}
		
		//	트리구성
		for(int i = NN-1; i > 0; i--){
			tree[i] = tree[i*2] * tree[i*2+1]; 
		}
		
		int one, two;
		
		one = two = 0;
		
		while ( one < M || two < K ) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if(a == 1){
				one++;
				
				//	트리 값 변경
				tree[NN+b-1] = c;
				
				int p = (NN+b-1) / 2;	//	값이 변경된 노드의 부모노드 index
				for(int i = p; i >= 1; i/=2){
					if(c == 0){
						tree[i] = 0;
					}else{
						tree[i] = tree[i*2] * tree[i*2+1];
					}					 
				}				
			}else{
				two++;
				
				//	트리 구간합
				long val = rangeValue(b, c, 1, 1, NN);
				if(val == 0){
					bw.write("0\n");
				}else{
					bw.write((val%1000000007)+"\n");
				}
			}
		}
		bw.flush();
		
		br.close();
		bw.close();
	}

	private static long rangeValue(int ql, int qr, int idx, int l, int r) {
		// TODO Auto-generated method stub
		
		//	ql qr < l r or l r < ql qr
		if(qr < l || r < ql){
			return 1;
		}
		
		//	ql < l r < qr
		if(ql <= l && r <= qr){
			return tree[idx];
		}
		
		long left = rangeValue(ql, qr, idx*2, l, (l+r)/2);
		if(left == 0) return 0;
		long right = rangeValue(ql, qr, idx*2+1, (l+r)/2+1, r);
		if(right == 0) return 0;
		return left * right;
	}
}

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

문제

문제

출처

ICPC

구간 곱 오류 좀 찾아주세요~~~

kenocis9 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말