10800번: 컬러볼

https://www.acmicpc.net/problem/10800


$O(n\lg n)$

먼저, 크기를 기준으로 오름차순 정렬한다.
그럼 (s[j]<s[i]인 최대 j에 대해 s[1...j] 누적합) - (c[k]=c[i]이고 k<=j인 s[k] 누적합)이 해당 플레이어의 점수이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 2e5;
int n, t[MXN + 1], r[MXN + 1], tot;
struct st {
    int c, s, idx;
}a[MXN];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &a[i].c, &a[i].s), a[i].idx = i;
    sort(a, a + n, [](st i, st j) {return i.s < j.s; });
    for (int i = 0, j = 0; i < n; i++) {
        for (; a[j].s < a[i].s; j++) tot += a[j].s, t[a[j].c] += a[j].s;
        r[a[i].idx] = tot - t[a[i].c];
    }
    for (int i = 0; i < n; i++) printf("%d\n", r[i]);
    return 0;
}