백준 : 10800

처음 로직은 맞았지만 크기가 2000인줄 착각해서 runtime 에러를 해결하지 못했다.

 

문제는 크기별로 정렬한뒤 누적사이즈 - 누적컬러사이즈[현재색갈]  을 빼주면 된다.

 

하지만 문제인것이 같은 색깔의 같은 사이즈가 나온다면 문제가없지만 

 

다른 색깔의 같은 사이즈가나오면 같은 크기는 제거하지 못한다 그것은 pivot을 만들어서 다른색갈이 나올때마다 크기별 사이즈들을 저장해서 해결했다.

 

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

public class 컬러볼 {
	static int N;

	static class Ball implements Comparable<Ball> {
		int color;
		int size;
		int num;

		public Ball(int color, int size, int num) {
			this.color = color;
			this.size = size;
			this.num = num;
		}

		@Override
		public int compareTo(Ball o) {
			if (size > o.size) {
				return 1;
			} else if (size == o.size) {
				return color - o.color;
			} else {
				return -1;
			}
		}
	}

	static long colorCnt[] = new long[200001];
	static long allCnt = 0;
	static long ans[] = new long[200001];
	static int sizeCnt[] = new int[200001];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[];

		N = Integer.parseInt(br.readLine());
		Ball ball[] = new Ball[N];
		for (int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			ball[i] = new Ball(Integer.parseInt(str[0]), Integer.parseInt(str[1]), i);
//			int c = (int) (Math.random() * 2000 +1);
//			int size = (int) (Math.random()* 2000 +1);
//			ball[i] = new Ball(c, size, i);

		}

		Arrays.sort(ball);

		// 이코드에서는 같은 size를 잡아먹는 경우가 있다.
		// 고치기 위해서는 같은 크기일경우 그사이즈만큼은 더빼주는걸로하자.
		int curSize = -1;
		int sizeNum = 0;
		for (int i = 0; i < N; i++) {
			if (curSize == ball[i].size) {
				ans[ball[i].num] -= curSize * sizeNum;
				ans[ball[i].num] += sizeCnt[ball[i].color] * curSize;
				sizeNum++;
			} else {
				Arrays.fill(sizeCnt, 0);
				curSize = ball[i].size;
				sizeNum = 1;
			}

			ans[ball[i].num] += allCnt - colorCnt[ball[i].color];
			allCnt += ball[i].size;
			colorCnt[ball[i].color] += ball[i].size;
			sizeCnt[ball[i].color]++;
		}

		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < N; i++) {
			sb.append(ans[i]).append('\n');
		}
		System.out.print(sb.toString());

	}
}