글 읽기 - 나무심기 문제 도와주세요 반례 필요합니다.

gaegul04 4년 전 0

아래의 코드로 하고 있는데, 채점 시작하자마자 실패가 되는데

반례 부탁드립니다.

package prostudy;
import java.io.*;
import java.util.*;;

/*
https://www.acmicpc.net/problem/1280
[입력]
 - 1~ N 개의 나무
 - N 개의 각 좌표 x[i]
 
[출력]
 - 2번 나무부터 N번 나무까지를 심는 비용의 곱을 출력

[풀이전략]

i번쨰 나무를 심을때, 두개의 구간으로 나누어 값을 계산한다
1) Left 구간
 - 1~x[i] 까지의 구간
   식으로 정리하면 xi>x1,x2, ... 이게 성립하므로
  (xi - x1) + (xi-x2) + ...
    = xi*cnt - (x1+...+xi)

2) Right 구간
 - x[i] ~ end 까지의 구간
   식으로 정리하면 x(i+1), x(i+2) > x(i) 이게 성립
    (xi+1 - xi) + (xi+2 -x) + ...
     = ( xi+1~ xn 까지의 구간합) - xi*cnt 
 */
public class bj1280나무심기 {
	public static int N, H;
	public static long[] cntTree, sumTree, position;
	public static final long MOD = 1000000007;
	public static final int MAXLEAF = 200001;
	public static long ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		position = new long[N+1];
		long cnt=0, sum=0, AnsL, AnsR;
		int positionV;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			position[i] = Integer.parseInt(st.nextToken());
		}
		init();
		for (int i = 1; i <= N; i++) {
			positionV= (int) position[i];
			
			if(i==1){
				updateSumTree(positionV, positionV);
				continue;
			}

			cnt = getCNTTree(0, positionV);
			sum = sumTree(0,positionV);
			AnsL = (positionV * cnt - sum);

			cnt = getCNTTree(positionV+1, MAXLEAF);
			sum = sumTree(positionV+1, MAXLEAF);
			AnsR = ( sum - positionV * cnt);
			
			ans =(AnsL+AnsR)%MOD*ans%MOD;
			updateSumTree(positionV, positionV);
		}
		System.out.println(ans);
	}
	private static void updateSumTree(int idx, long val) {
		idx +=H;
		sumTree[idx] = val;
		cntTree[idx]++;
		while(idx>1) {
			idx/=2;
			sumTree[idx] = sumTree[idx*2]+sumTree[idx*2+1];
			cntTree[idx] = cntTree[idx*2]+cntTree[idx*2+1];
		}
	}

	private static long sumTree(int left, int right) {
		long ret = 0;
		left+=H;
		right+=H;
		while(left<=right) {
			if(left%2==1) {
				ret += sumTree[left++];
			}
			if(right%2==0) {
				ret += sumTree[right--];
			}
			left/=2;
			right/=2;
		}
		return ret;
	}
	private static long getCNTTree(int left, int right) {
		long ret = 0;
		left+=H;
		right+=H;
		while(left<=right) {
			if(left%2==1) {
				ret += cntTree[left++];
			}
			if(right%2==0) {
				ret += cntTree[right--];
			}
			left/=2;
			right/=2;
		}
		return ret;
	}
	private static void init() {
		H=1;
		while(H<MAXLEAF)
			H*=2;
		
		cntTree = new long[H*2];
		sumTree = new long[H*2];
		ans = 1;
	}

}

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

문제

문제

출처

ICPC

나무심기 문제 도와주세요 반례 필요합니다.

gaegul04 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말