Submission #170348

#	Time	Username	Problem	Language	Result	Execution time	Memory
170348		ngmh	사회적 불평등 (TOKI14_social)	C++11	100 / 100	126 ms	3356 KiB

social

#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> pi;

long long ls(long long x){ return (x)&(-x); }

long long n, t, fwmul[10005], fwf[10005], fws[10005], fwc[10005];
pi a[100000];

void pu(long long *tree, long long x, long long y){
    for(; x <= 10001; x += ls(x)) tree[x] += y;
}
long long pq(long long *tree, long long x){
    long long t = 0;
    for(; x; x -= ls(x)) t += tree[x];
    return t;
}
long long rq(long long *tree, long long s, long long e){
    return pq(tree, e)-pq(tree, s-1);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    sort(a, a+n);
    for(int i = 0; i < n; i++){
        //cur: b, d
        //prev: a, c
        //d > c: bd+ac-bc-ad
        t += a[i].first*a[i].second*rq(fwc, 1, a[i].second-1)+rq(fwmul, 1, a[i].second-1); //bd+ac
        t -= a[i].first*rq(fws, 1, a[i].second-1)+rq(fwf, 1, a[i].second-1)*a[i].second; //-bc-ad
        //c > d: bc+ad-ac-bd
        t += a[i].first*rq(fws, a[i].second+1, 10001)+rq(fwf, a[i].second+1, 10001)*a[i].second; //bc+ad
        t -= a[i].first*a[i].second*rq(fwc, a[i].second+1, 10001)+rq(fwmul, a[i].second+1, 10001); //-bd-ac
        //update
        pu(fwmul, a[i].second, a[i].first*a[i].second);
        pu(fwf, a[i].second, a[i].first);
        pu(fws, a[i].second, a[i].second);
        pu(fwc, a[i].second, 1);
    }
    cout << t;
}

• Subtask 1: 29 / 29
• Subtask 2: 19 / 19
• Subtask 3: 20 / 20
• Subtask 4: 32 / 32