Kevin_Zhang

Untitled

Jan 13th, 2021
569
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define pb emplace_back
  3. #define AI(i) begin(i), end(i)
  4. template<class T>
  5. bool chmax(T &val, T nv) {
  6.     return val < nv ? (val = nv, true) : false;
  7. }
  8. template<class T>
  9. bool chmin(T &val, T nv) {
  10.     return nv < val ? (val = nv, true) : false;
  11. }
  12. using namespace std;
  13. using ll = long long;
  14. #ifdef KEV
  15. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  16. void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
  17. void kout(){ cerr << endl; }
  18. template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
  19. #else
  20. #define DE(...) 0
  21. #define debug(...) 0
  22. #endif
  23. // What I should check
  24. // 1. overflow
  25. // 2. corner cases
  26. // Enjoy the problem instead of hurrying to AC
  27. // Good luck !
  28. const int MAX_N = 200010;
  29.  
  30. #include <bits/extc++.h>
  31. using namespace __gnu_pbds;
  32.  
  33. using bst = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
  34.  
  35.  
  36.  
  37. ll solve(bst &pa) {
  38.     bst now;
  39.     int p;
  40.     cin >> p;
  41.     // branch
  42.     ll res = 0;
  43.     if (p == 0) {
  44.         res += solve(now);
  45.         res += solve(now);
  46.     }
  47.     // leaf
  48.     else {
  49.         now.insert(p);
  50.     }
  51.     if (pa.empty()) {
  52.         pa.swap(now);
  53.     }
  54.     else {
  55.         if (now.size() > pa.size()) pa.swap(now);
  56.         ll f = 0, b = 0;
  57.         for (int u : now) {
  58.             int k = pa.order_of_key(u);
  59.             f += k, b += pa.size() - k;
  60.         }
  61.         res += min(f, b);
  62.         for (int u : now)
  63.             pa.insert(u);
  64.     }
  65.     return res;
  66. }
  67. int32_t main() {
  68.     ios_base::sync_with_stdio(0), cin.tie(0);
  69.     int n;
  70.     cin >> n;
  71.     bst _;
  72.     cout << solve(_) << '\n';
  73. }
RAW Paste Data