Advertisement
YEZAELP

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

Feb 25th, 2021
157
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None
  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.  
Advertisement
RAW Paste Data Copied
Advertisement