글 읽기 - 왜 출력초과인지ㅠㅠ

filot 6년 전 2

왜 출력초과라고 뜨는지 모르겠네요

M + K만큼 질의를 수행하면 되는거 아닌가요?

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

public class Main {
	static int N;
	static int M;
	static int K;
	static int LEAF_COUNT;
	static int TOTAL;
	static int START;
	static int MOD = 1000000007;
	static long[] ST;
	
	public static void main(String[] args) throws Exception {		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		
		String[] input = reader.readLine().split(" ");
		
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		K = Integer.parseInt(input[2]);
		
		LEAF_COUNT = calculateLeafCount();
		TOTAL = LEAF_COUNT * 2;
		START = (TOTAL / 2) - 1;
		
		ST = new long[TOTAL + 1];
		
		for (int i = 1; i <= N; i++)
			ST[i + START] = Integer.parseInt(reader.readLine());
		
		for (int i = START; i >= 1; i--)	 {
			long left = ST[i + i] % MOD;
			long right = ST[i + i + 1] % MOD;
			
			ST[i] = (left * right) % MOD;
		}
		
		for (int i = 1; i <= M + K; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if (a == 1)
				update(b, c);
			else
				writer.println(RMQ(b, c));
		}
		
		writer.close();
		reader.close();
	}

	private static int calculateLeafCount() {
		int i = 1;
		
		while (i < N)
			i *= 2;
		
		return i;
	}
	
	private static long RMQ(int a, int b) {
		int from = START + a;
		int to = START + b;
		long Answer = 1;
		
		while (from <= to) {
			if (from % 2 == 1) {
				Answer *= ST[from] % MOD;				
				from++;
			}
			
			if (to % 2 == 0) {
				Answer *= ST[to] % MOD;
				to--;
			}
			
			from /= 2;
			to /= 2;
		}
		
		return Answer;
	}
	
	private static void update(int a, int b) {
		ST[START + a] = b;
		
		for (int i = (START + a) / 2; i >= 1; i /= 2) {
			long left = ST[i + i] % MOD;
			long right = ST[i + i + 1] % MOD;
			
			ST[i] = (left * right) % MOD;
		}
	}
	
}

rhsek123 1년 전 1

Answer *= ST[from] % MOD;		
// 에서 long 의 범위를 초과될 수 있습니다.
// Answer %= MOD; 바로 아래 이 코드를 추가해주셔야 합니다. 
// 저도 똑같은 이유로 출력초과가 나와서 통과 후 적습니다.

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

문제

문제

출처

ICPC

왜 출력초과인지ㅠㅠ

filot 6년 전 2

rhsek123 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말