Advertisement
Guest User

Lunch Court

a guest
Mar 20th, 2021
604
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. class Fenwick {
  6.     private:
  7.         vector<ll> val;
  8.     public:
  9.         Fenwick(int n) : val(n+1, 0) {}
  10.  
  11.         // Adds v to index i
  12.         void add(int i, ll v) {
  13.             for (++i; i < val.size(); i += i & -i) {
  14.                 val[i] += v;
  15.             }
  16.         }
  17.  
  18.         // Calculates prefix sum up to index i
  19.         ll get(int i) {
  20.             ll res = 0;
  21.             for (++i; i > 0; i -= i & -i) {
  22.                 res += val[i];
  23.             }
  24.             return res;
  25.         }
  26.         ll get(int a, int b) { return get(b) - get(a-1); }
  27. };
  28.  
  29. // Segment tree for range minimum and addition.
  30. class SegTree {
  31.     private:
  32.         const ll NEUT = 4 * (ll)1e18;
  33.         vector<ll> seg, tag;
  34.         int h = 1;
  35.  
  36.         void apply(int i, ll v) {
  37.             seg[i] += v;
  38.             if (i < h) tag[i] += v;
  39.         }
  40.         void push(int i) {
  41.             if (tag[i] == 0) return;
  42.             apply(2*i, tag[i]);
  43.             apply(2*i+1, tag[i]);
  44.             tag[i] = 0;
  45.         }
  46.         ll combine(ll a, ll b) { return min(a, b); }
  47.  
  48.         ll recGet(int a, int b, int i, int ia, int ib) {
  49.             if (ib <= a || b <= ia) return NEUT;
  50.             if (a <= ia && ib <= b) return seg[i];
  51.             push(i);
  52.             int im = (ia + ib) >> 1;
  53.             return combine(
  54.                 recGet(a, b, 2*i, ia, im),
  55.                 recGet(a, b, 2*i+1, im, ib));
  56.         }
  57.         void recApply(int a, int b, ll v, int i, int ia, int ib) {
  58.             if (ib <= a || b <= ia) return;
  59.             if (a <= ia && ib <= b) apply(i, v);
  60.             else {
  61.                 push(i);
  62.                 int im = (ia + ib) >> 1;
  63.                 recApply(a, b, v, 2*i, ia, im);
  64.                 recApply(a, b, v, 2*i+1, im, ib);
  65.                 seg[i] = combine(seg[2*i], seg[2*i+1]);
  66.             }
  67.         }
  68.         int recFind(int a, int b, ll v, int i, int ia, int ib) {
  69.             if (seg[i] > v) return b;
  70.             if (b <= ia || ib <= a) return b;
  71.             if (ib == ia + 1) return ia;
  72.  
  73.             push(i);
  74.             int im = (ia + ib) >> 1;
  75.             int off = recFind(a, b, v, 2*i, ia, im);
  76.             if (off < b) return off;
  77.             else return recFind(a, b, v, 2*i+1, im, ib);
  78.         }
  79.     public:
  80.         SegTree(int n) {
  81.             while(h < n) h *= 2;
  82.             seg.resize(2*h, 0);
  83.             tag.resize(h, 0);
  84.         }
  85.         ll rangeMin(int a, int b) { return recGet(a, b+1, 1, 0, h); }
  86.         void rangeAdd(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
  87.         int findNext(int a, int b, ll v) { return recFind(a, b+1, v, 1, 0, h); }
  88. };
  89.  
  90.  
  91. struct SegTreeBeats {
  92.     private:
  93.         const ll INF = 4 * (ll)1e18;
  94.         vector<ll> add, cap;
  95.         int h = 1;
  96.  
  97.         void apply(int i, ll a, ll c) {
  98.             cap[i] = min(cap[i] + a, c);
  99.             if (i < h) add[i] += a;
  100.         }
  101.         void push(int i) {
  102.             apply(2*i, add[i], cap[i]);
  103.             apply(2*i+1, add[i], cap[i]);
  104.             add[i] = 0;
  105.             cap[i] = INF;
  106.         }
  107.  
  108.         void recAdd(int a, int b, ll v, int i, int ia, int ib) {
  109.             if (ib <= a || b <= ia) return;
  110.             else if (a <= ia && ib <= b) apply(i, v, INF);
  111.             else {
  112.                 push(i);
  113.                 int im = (ia + ib) >> 1;
  114.                 recAdd(a, b, v, 2*i, ia, im);
  115.                 recAdd(a, b, v, 2*i+1, im, ib);
  116.             }
  117.         }
  118.         ll recMax(int a, int b, int i, int ia, int ib) {
  119.             if (ib <= a || b <= ia) return -INF;
  120.             if (a <= ia && ib <= b) return cap[i];
  121.            
  122.             push(i);
  123.             int im = (ia + ib) >> 1;
  124.             return max(recMax(a, b, 2*i, ia, im), recMax(a, b, 2*i+1, im, ib));
  125.         }
  126.     public:
  127.         SegTreeBeats(int n) {
  128.             while(h < n) h <<= 1;
  129.             add.resize(h, 0);
  130.             cap.resize(2*h, 0);
  131.         }
  132.  
  133.         void rangeAdd(int a, int b, ll v) { recAdd(a, b+1, v, 1, 0, h); apply(1, 0, 0); }
  134.         ll get(int i) { return recMax(i, i+1, 1, 0, h); }
  135. };
  136.  
  137. int main() {
  138.     ios_base::sync_with_stdio(false);
  139.     cin.tie(0);
  140.  
  141.     int n, m, q;
  142.     cin >> n >> m >> q;
  143.  
  144.     SegTreeBeats cur(n);
  145.     Fenwick tot(n+1);
  146.  
  147.     vector<int> res;
  148.     vector<vector<pair<ll, int>>> qs(n);
  149.     vector<array<ll, 5>> ops(q);
  150.  
  151.     for (int qi = 0; qi < q; ++qi) {
  152.         cin >> ops[qi][0];
  153.        
  154.         ll a, b;
  155.         cin >> a >> b;
  156.         --a; --b;
  157.         ops[qi][1] = a; ops[qi][2] = b;
  158.  
  159.         if (ops[qi][0] == 1) {
  160.             ll c, k;
  161.             cin >> c >> k;
  162.             ops[qi][3] = c; ops[qi][4] = k;
  163.  
  164.             cur.rangeAdd(a, b, -k);
  165.             tot.add(a, k);
  166.             tot.add(b+1, -k);
  167.  
  168.         } else if (ops[qi][0] == 2) {
  169.             ll k;
  170.             cin >> k;
  171.             ops[qi][3] = k;
  172.  
  173.             cur.rangeAdd(a, b, k);
  174.  
  175.         } else if (ops[qi][0] == 3) {
  176.             ++b;
  177.             ll v = -cur.get(a);
  178.  
  179.             int ind = res.size();
  180.             res.emplace_back(0);
  181.             if (v >= b) qs[a].emplace_back(tot.get(a) - (v - b), ind);
  182.         }
  183.  
  184.     }
  185.  
  186.     const ll INF = 1e18;
  187.     SegTree groups(n);
  188.     vector<int> inds(n, 0);
  189.     for (int i = 0; i < n; ++i) {
  190.         if (qs[i].empty()) {
  191.             groups.rangeAdd(i, i, INF);
  192.         } else {
  193.             sort(qs[i].begin(), qs[i].end());
  194.             groups.rangeAdd(i, i, qs[i][0].first);
  195.         }
  196.     }
  197.  
  198.     for (int qi = 0; qi < q; ++qi) {
  199.         int t = ops[qi][0];
  200.         if (t == 1) {
  201.             ll a = ops[qi][1]; ll b = ops[qi][2];
  202.             ll c = ops[qi][3]; ll k = ops[qi][4];
  203.  
  204.             groups.rangeAdd(a, b, -k);
  205.             while(true) {
  206.                 int j = groups.findNext(0, n-1, 0);
  207.                 if (j == n) break;
  208.  
  209.                 res[qs[j][inds[j]].second] = c;
  210.                 ++inds[j];
  211.                 if (inds[j] >= qs[j].size()) {
  212.                     groups.rangeAdd(j, j, INF);
  213.                 } else {
  214.                     groups.rangeAdd(j, j, qs[j][inds[j]].first - qs[j][inds[j] - 1].first);
  215.                 }
  216.             }
  217.         }
  218.     }
  219.  
  220.     for (auto c : res) cout << c << '\n';
  221. }
  222.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement