fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. namespace std {
  6. #ifndef LOCAL
  7. #define cerr \
  8.   if (0) cerr
  9. #endif
  10. #define sz(x) ((int)(x.size()))
  11. }  // namespace std
  12.  
  13. const int Q = 500'005;
  14. const int N = 3 * Q;
  15.  
  16. int64_t get_sum(int l, int r) {
  17.   return 1ll * (l + r) * (r - l + 1) / 2;
  18. }
  19.  
  20. struct Node {
  21.   int cnt;
  22.   int64_t sum;
  23.   Node(int cnt = 0, int64_t sum = 0) : cnt(cnt), sum(sum) {}
  24.   Node operator+(const Node& rhs) const {
  25.     return Node(cnt + rhs.cnt, sum + rhs.sum);
  26.   }
  27.   Node& operator+=(const Node& rhs) {
  28.     cnt += rhs.cnt;
  29.     sum += rhs.sum;
  30.     return *this;
  31.   }
  32.   Node operator-(const Node& rhs) const {
  33.     return Node(cnt - rhs.cnt, sum - rhs.sum);
  34.   }
  35. };
  36.  
  37. int q;
  38. array<int, 3> qr[Q];
  39. int prv[N], nxt[N];
  40. pair<int, int> segs_at[N];
  41. pair<int, int> new_segs[N];
  42. int index_seg[N];
  43. Node ft[N];
  44.  
  45. int32_t main() {
  46.   ios_base::sync_with_stdio(0);
  47.   cin.tie(0);
  48. #ifdef LOCAL
  49. #define task "a"
  50. #else
  51. #define task "TSEQ"
  52. #endif
  53.   if (fopen(task ".inp", "r")) {
  54.     freopen(task ".inp", "r", stdin);
  55.     freopen(task ".out", "w", stdout);
  56.   }
  57.   cin >> q;
  58.   set<array<int, 3>> segs;
  59.   segs.insert({0, 0, 1});
  60.   segs_at[1] = {0, 0};
  61.   int low = 1;
  62.   int idx = 1;
  63.   for (int i = 1; i <= q; i++) {
  64.     for (int j = 0; j < 3; j++) {
  65.       cin >> qr[i][j];
  66.     }
  67.     auto rematch = [&](int pos, vector<pair<int, int>> x) {
  68.       vector<pair<int, int>> nx;
  69.       for (auto [l, r] : x) {
  70.         if (l <= r) {
  71.           nx.emplace_back(l, r);
  72.         }
  73.       }
  74.       nx.swap(x);
  75.       int curr = idx + 1;
  76.       prv[curr] = prv[pos];
  77.       nxt[prv[pos]] = curr;
  78.       for (int j = 1; j < sz(x); j++) {
  79.         prv[curr + j] = curr + j - 1;
  80.         nxt[curr + j - 1] = curr + j;
  81.       }
  82.       if (nxt[pos]) {
  83.         prv[nxt[pos]] = curr + sz(x) - 1;
  84.         nxt[curr + sz(x) - 1] = nxt[pos];
  85.       }
  86.       for (int j = 0; j < sz(x); j++) {
  87.         segs.insert({x[j].first, x[j].second, curr + j});
  88.         segs_at[curr + j] = {x[j].first, x[j].second};
  89.       }
  90.       idx += sz(x);
  91.     };
  92.     if (qr[i][0] == 1) {
  93.       auto [_, x, k] = qr[i];
  94.       int high = low + k - 1;
  95.       auto it = segs.upper_bound(array<int, 3>{x, (int)1e9, (int)1e9});
  96.       assert(it != segs.begin());
  97.       it--;
  98.       auto [l, r, pos] = *it;
  99.       assert(r >= x);
  100.       // [l, x] -> [low, high] -> [x + 1, r]
  101.       // cerr << "1split " << l << " " << r << "into ["
  102.       //      << l << " " << x << "] ["
  103.       //      << low << " " << high << "] ["
  104.       //      << x + 1 << " " << r << "]\n";
  105.       rematch(pos, {{l, x}, {low, high}, {x + 1, r}});
  106.       segs.erase({l, r, pos});
  107.       low += k;
  108.     }
  109.     if (qr[i][0] == 2) {
  110.       auto [_, y, h] = qr[i];
  111.       auto it = segs.upper_bound(array<int, 3>{y, (int)1e9});
  112.       assert(it != segs.begin());
  113.       it--;
  114.       auto [l, r, pos] = *it;
  115.       assert(r >= y);
  116.       rematch(pos, {{l, y}, {y + 1, r}});
  117.       segs.erase({l, r, pos});
  118.     }
  119.   }
  120.   int num_segs = 0;
  121.   for (int i = 0; (i = nxt[i]);) {
  122.     new_segs[++num_segs] = segs_at[i];
  123.     index_seg[num_segs] = num_segs;
  124.   }
  125.   for (int i = 1; i <= num_segs; i++) {
  126.     segs_at[i] = new_segs[i];
  127.   }
  128.   sort(index_seg + 1, index_seg + num_segs + 1, [&](int i, int j) { return segs_at[i].second < segs_at[j].second; });
  129.   auto update = [&](int i, int delta) {
  130.     auto [l, r] = segs_at[i];
  131.     if (l > r) return;
  132.     Node curr = Node((r - l + 1) * delta, get_sum(l, r) * delta);
  133.     while (i <= num_segs) {
  134.       ft[i] += curr;
  135.       i += i & -i;
  136.     }
  137.   };
  138.   auto get = [&](int i) -> Node {
  139.     Node curr(0, 0);
  140.     while (i > 0) {
  141.       curr += ft[i];
  142.       i -= i & -i;
  143.     }
  144.     return curr;
  145.   };
  146.   auto lowerbound = [&](int v) -> int {
  147.     int cnt = 0;
  148.     int pos = 0;
  149.     for (int i = 20; i >= 0; i--) {
  150.       if (pos + (1 << i) <= num_segs && cnt + ft[pos + (1 << i)].cnt < v) {
  151.         pos += 1 << i;
  152.         cnt += ft[pos].cnt;
  153.       }
  154.     }
  155.     return pos + 1;
  156.   };
  157.   auto get_prefix = [&](int l) -> int64_t {
  158.     if (l == 0) {
  159.       return 0LL;
  160.     }
  161.     int pos = lowerbound(l);
  162.     auto [curr_cnt, curr_sum] = get(pos);
  163.     auto [lo, hi] = segs_at[pos];
  164.     curr_cnt -= l;
  165.     if (curr_cnt) {
  166.       curr_sum -= get_sum(hi - curr_cnt + 1, hi);
  167.     }
  168.     return curr_sum;
  169.   };
  170.   low = 1;
  171.   int j = 1;
  172.   for (int i = 1; i <= q; i++) {
  173.     while (j <= num_segs && segs_at[index_seg[j]].second < low) {
  174.       update(index_seg[j], 1);
  175.       j++;
  176.     }
  177.     if (qr[i][0] == 1) {
  178.       auto [_, x, k] = qr[i];
  179.       low += k;
  180.     }
  181.     if (qr[i][0] == 2) {
  182.       auto [_, y, h] = qr[i];
  183.       int lo = 1, hi = num_segs;
  184.       int ans = -1;
  185.       while (lo <= hi) {
  186.         int mid = (lo + hi) >> 1;
  187.         if (segs_at[index_seg[mid]].second <= y) {
  188.           ans = mid;
  189.           lo = mid + 1;
  190.         } else {
  191.           hi = mid - 1;
  192.         }
  193.       }
  194.       // cerr<<"que "<<_<<" "<<y<<" "<<h<<": " <<
  195.       assert(ans != -1 && ans < num_segs);
  196.       ans = index_seg[ans];
  197.       int trc = get(ans).cnt;
  198.       int can = trc + h;
  199.       int pos = lowerbound(can);
  200.       int dem = 0;
  201.       for (int j = ans + 1; j < pos; j++) {
  202.         int curr = get(j).cnt - get(j - 1).cnt;
  203.         if (!curr) continue;
  204.         h -= curr;
  205.         update(j, -1);
  206.         segs_at[j].first = 1e9;
  207.       }
  208.       auto& [l, r] = segs_at[pos];
  209.       assert(get(pos).cnt - get(pos - 1).cnt > 0);
  210.       update(pos, -1);
  211.       l += h;
  212.       update(pos, 1);
  213.     }
  214.     if (qr[i][0] == 3) {
  215.       auto [_, l, r] = qr[i];
  216.       cout << get_prefix(r) - get_prefix(l - 1) << "\n";
  217.     }
  218.   }
  219.   return 0;
  220. }
  221.  
Success #stdin #stdout 0.01s 30248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pqQQ4U
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!