oj.uz

Submission #170348

# Submission time Handle Problem Language Result Execution time Memory
170348 2019-12-24T20:22:40 Z ngmh 사회적 불평등 (TOKI14_social) C++11
100 / 100
 126 ms 3356 KB 
#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.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 508 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1528 KB Output is correct
2 Correct 39 ms 1528 KB Output is correct
3 Correct 33 ms 1272 KB Output is correct
4 Correct 36 ms 1272 KB Output is correct
5 Correct 41 ms 1516 KB Output is correct
6 Correct 37 ms 1400 KB Output is correct
7 Correct 33 ms 1276 KB Output is correct
8 Correct 33 ms 1272 KB Output is correct
9 Correct 39 ms 1400 KB Output is correct
10 Correct 42 ms 1528 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1708 KB Output is correct
2 Correct 44 ms 1516 KB Output is correct
3 Correct 38 ms 1400 KB Output is correct
4 Correct 52 ms 1624 KB Output is correct
5 Correct 40 ms 1528 KB Output is correct
6 Correct 43 ms 1528 KB Output is correct
7 Correct 46 ms 1784 KB Output is correct
8 Correct 47 ms 1912 KB Output is correct
9 Correct 41 ms 1528 KB Output is correct
10 Correct 50 ms 1784 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1200 KB Output is correct
2 Correct 102 ms 2876 KB Output is correct
3 Correct 89 ms 2580 KB Output is correct
4 Correct 46 ms 1528 KB Output is correct
5 Correct 57 ms 1912 KB Output is correct
6 Correct 87 ms 2540 KB Output is correct
7 Correct 74 ms 2388 KB Output is correct
8 Correct 99 ms 2812 KB Output is correct
9 Correct 112 ms 3356 KB Output is correct
10 Correct 126 ms 3192 KB Output is correct