# PROG-1109: คู่ตัวเลขเด่น (Pair)

Feb 25th, 2021
157
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. using lli = long long;
6. using pll = pair <lli, lli>;
7. const int N = 2*(1<<18);
8. int n;
9. lli mx = 0;
10. pll ab[100010];
11. pll tree[N];// sum, cnt
12.
13. pll update(int idx, lli l, lli r, lli pos, lli add){
14.     if(l == r) return tree[idx] = make_pair(add, 1);
15.     lli mid = (l + r)/ 2;
16.     if(pos <= mid){
17.         pll upd = update(2*idx, l, mid, pos, add);
18.         return tree[idx] = make_pair(upd.first + tree[2*idx+1].first, upd.second + tree[2*idx+1].second);
19.     }
20.     pll upd = update(2*idx+1, mid+1, r, pos, add);
21.     return tree[idx] = make_pair(tree[2*idx].first + upd.first, tree[2*idx].second + upd.second);
22. }
23.
24. pll query(int idx, lli l, lli r, lli s, lli e){
25.     if(r < s or l > e) return make_pair(0, 0);
26.     if(s <= l and r <= e) return tree[idx];
27.     lli mid = (l + r)/ 2;
28.     pll Left = query(2*idx, l, mid, s, e);
29.     pll Right = query(2*idx+1, mid+1, r, s, e);
30.     return make_pair(Left.first + Right.first, Left.second + Right.second);
31. }
32.
33. int main(){
34.
35.     scanf("%d", &n);
36.
37.     for(int i=1;i<=n;i++){
38.         lli a, b;
39.         scanf("%lld%lld", &a, &b);
40.         ab[i] = make_pair(a, b);
41.         mx = max(mx, b);
42.     }
43.
44.     sort(ab + 1, ab + n + 1, greater <pll> ());
45.
46.     lli sum = 0;
47.     for(int i=1;i<=n;i++){
48.         pll x = query(1, 1, mx, 1, ab[i].second-1);
49.         if(x.second > 0) sum += (lli) x.first + (ab[i].first * x.second);
50.         update(1, 1, mx, ab[i].second, ab[i].first);
51.     }
52.
53.     printf("%lld", sum);
54.
55.     return 0;
56. }
57.