글 읽기 - 왜 틀린걸까요 ㅜㅜ.. long 부분만 한시간 반째 고치고 있습니다...

meringueee 4년 전 0

아래 코드인데... 자료형 말고는 걸릴 만한 부분이 없다 생각했는데 왠지 자꾸 뜨네요...ㅜㅜ

혹시 어디가 문제인 지 한 번 짚어주실 수 있을까요 ㅜㅜ???

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

public class BJ1280_1 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	static int n;
	static long sum[];
	static int cnt[];
	
	static long ans;
	static final long mod = 1000000007;
	static final int size = 262144;
	public static void main(String[] args) throws NumberFormatException, IOException {
		n = Integer.parseInt(br.readLine().trim());
		
		sum = new long[size*2];
		cnt = new int[size*2];
		
		ans = 1;
		add(Integer.parseInt(br.readLine().trim())); //add 1st tree
		for(int i=2; i<=n; i++) {
			int x = Integer.parseInt(br.readLine().trim());
			long belowSum = sumsum(0,x-1);
			long upperSum = sumsum(x+1,200000);
			int belowCnt = sumcnt(0, x-1);
			int upperCnt = sumcnt(x+1, 200000);
			
			long a = upperSum - ((long)upperCnt)*x;
			long b = ((long)belowCnt)*x -belowSum;
			a%=mod;
			b%=mod;
			ans = (ans * ((a+b)%mod)) % mod;
			
			add(x);
		}
		
		System.out.println(ans);
	}
	private static int sumcnt(int ss, int ee) {
		int s = size+ss;
		int e = size+ee;
		
		int ret = 0;
		while(s<=e) {
			if(s%2 == 1) {
				ret+= cnt[s++];
			}
			if(e%2 == 0) {
				ret+= cnt[e--];
			}
			s/=2; e/=2;			
		}
		
		return ret;
	}
	private static long sumsum(int ss, int ee) {
		int s = size+ss;
		int e = size+ee;
		
		long ret = 0;
		while(s<=e) {
			if(s%2 == 1) {
				ret+= sum[s++];
			}
			if(e%2 == 0) {
				ret+= sum[e--];
			}
			s/=2; e/=2;			
		}
		
		return ret%mod;
	}
	private static void add(int x) {
		cnt[size+x]++;
		sum[size+x]+=x;
		cntupd(size+x);
		sumupd(size+x);
	}
	private static void sumupd(int x) {
		while(x>1) {
			x/=2;
			sum[x] = sum[x*2]+sum[x*2+1];
		}
	}
	private static void cntupd(int x) {
		while(x>1) {
			x/=2;
			cnt[x] = cnt[x*2]+cnt[x*2+1];
		}
	}
	

}

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

문제

문제

출처

ICPC

왜 틀린걸까요 ㅜㅜ.. long 부분만 한시간 반째 고치고 있습니다...

meringueee 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말