Submission #739819

#	Time	Username	Problem	Language	Result	Execution time	Memory
739819		cig32	Food Court (JOI21_foodcourt)	C++17	100 / 100	694 ms	151244 KiB

foodcourt

#include "bits/stdc++.h"
using namespace std;
#define int long long
struct segtree_basic {
  struct node {
    int lazyval, mi, ma, sum; char lazytag;
    int len; // not changing
  };
  int stok;
  vector<node> st;
  void bu(int l, int r, int idx) {
    st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
    st[idx].lazytag = '?';
    st[idx].len = r - l + 1;
    if(l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    bu(l, mid, 2*idx+1);
    bu(mid+1, r, 2*idx+2);
  }
  void push_down(int idx) {
    if(st[idx].lazytag == '?') return;
    if(st[idx].lazytag == ':') {
      st[2*idx+1].lazyval = st[idx].lazyval;
      st[2*idx+1].mi = st[idx].lazyval;
      st[2*idx+1].ma = st[idx].lazyval;
      st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = ':';
 
      st[2*idx+2].lazyval = st[idx].lazyval;
      st[2*idx+2].mi = st[idx].lazyval;
      st[2*idx+2].ma = st[idx].lazyval;
      st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = ':';
 
    }
    else {
      st[2*idx+1].lazyval += st[idx].lazyval;
      st[2*idx+1].mi += st[idx].lazyval;
      st[2*idx+1].ma += st[idx].lazyval;
      st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
 
      st[2*idx+2].lazyval += st[idx].lazyval;
      st[2*idx+2].mi += st[idx].lazyval;
      st[2*idx+2].ma += st[idx].lazyval;
      st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
    }
    st[idx].lazytag = '?';
    st[idx].lazyval = 0;
  }
  void push_up(int idx) {
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
    st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
  }
  void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
    if(l <= constl && constr <= r) {
      st[idx].lazyval = val;
      st[idx].mi = val;
      st[idx].ma = val;
      st[idx].sum = val * st[idx].len;
      st[idx].lazytag = ':';
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
    else {
      u1(l, r, constl, mid, 2*idx+1, val);
      u1(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
    if(l <= constl && constr <= r) {
      st[idx].lazyval += val;
      st[idx].mi += val;
      st[idx].ma += val;
      st[idx].sum += val * st[idx].len;
      st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
    else {
      u2(l, r, constl, mid, 2*idx+1, val);
      u2(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  int qu1(int l, int r, int constl, int constr, int idx) { // range min
    if(l <= constl && constr <= r) return st[idx].mi;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid + 1) return qu1(l, r, constl, mid, 2*idx+1);
    else {
      return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
    }
  }
 
  int qu2(int l, int r, int constl, int constr, int idx) { // range max
    if(l <= constl && constr <= r) return st[idx].ma;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2); 
    else if(constr < l || r < mid + 1) return qu2(l, r, constl, mid, 2*idx+1);
    else {
      return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
    }
  }
  int qu3(int l, int r, int constl, int constr, int idx) { // range sum
    if(l <= constl && constr <= r) return st[idx].sum;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu3(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid + 1) return qu3(l, r, constl, mid, 2*idx+1);
    else {
      return qu3(l, r, constl, mid, 2*idx+1) + qu3(l, r, mid+1, constr, 2*idx+2);
    }
  }
  int qu4(int l, int r, int constl, int constr, int idx, int val) { // first at least v
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].ma >= val) constr = mid, idx = 2*idx + 1;
        else constl = mid+1, idx = 2*idx + 2;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu4(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu4(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu4(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu4(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  int qu5(int l, int r, int constl, int constr, int idx, int val) { // first at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].mi <= val) constr = mid, idx = 2*idx + 1;
        else constl = mid+1, idx = 2*idx + 2;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu5(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu5(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu5(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu5(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  int qu6(int l, int r, int constl, int constr, int idx, int val) { // last at least v
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].ma >= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu6(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu6(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu6(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu6(l, r, constl, mid, 2*idx+1, val);
    }
  }
  int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu7(l, r, constl, mid, 2*idx+1, val);
    }
  }
  int qu8(int l, int r, int constl, int constr, int idx, int val) { // first partial sum at least v, only works when partial sum is non-decreasing
    if(l <= constl && constr <= r) {
      if(st[idx].sum < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].sum >= val) {
          idx = 2*idx+1, constr = mid;
        }
        else {
          val -= st[2*idx+1].sum;
          idx = 2*idx+2, constl = mid+1;
        }
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu8(l, r, mid+1, constr, 2*idx+2, val - st[2*idx+1].sum);
    else if(constr < l || r < mid+1) return qu8(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu8(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu8(l, r, mid+1, constr, 2*idx+2, val - st[2*idx+1].sum);
    }
  }
  public:
  void resize(int k) {
    st.resize(4*k + 10);
    stok = k;
    bu(0, k, 0);
  }
  void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
 
  void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
 
  int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
 
  int query_max(int l, int r) { return qu2(l, r, 0, stok, 0); }
 
  int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
 
  int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
 
  int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
 
  int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); } 
 
  int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }

  int query_firstPSAtLeast(int l, int r, int v) { return qu8(l, r, 0, stok, 0, v); }
};
struct segtree_bruh {
  struct node {
    int mss = 0, sum = 0, id;
  };
  vector<node> st;
  int stok;
  void push_up(int idx) {
    st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
    st[idx].mss = max(st[2*idx+2].mss, st[2*idx+1].mss + st[2*idx+2].sum);
    if(st[2*idx+2].mss < st[2*idx+1].mss + st[2*idx+2].sum) st[idx].id = st[2*idx+1].id;
    else st[idx].id = st[2*idx+2].id;
  }
  void init(int l, int r, int idx) {
    if(l == r) {
      st[idx].id = l;
      return;
    }
    int m = (l + r) >> 1;
    init(l, m, (idx << 1) + 1);
    init(m + 1, r, (idx << 1) + 2);
    push_up(idx);
  }
  void u(int l, int r, int tar, int idx, int val) {
    if(l == r) {
      st[idx].sum += val;
      st[idx].mss = max(st[idx].sum, 0ll);
      return;
    }
    int mid = (l + r) >> 1;
    if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
    else u(mid+1, r, tar, 2*idx+2, val);
    push_up(idx);
  }

  pair<pair<int, int>, int> qu(int l, int r, int constl, int constr, int idx) {
    if(l <= constl && constr <= r) return {{st[idx].mss, st[idx].id}, st[idx].sum};
    int mid = (constl + constr) >> 1;
    if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
    else {
      pair<pair<int, int>, int> lc = qu(l, r, constl, mid, 2*idx+1);
      pair<pair<int, int>, int> rc = qu(l, r, mid+1, constr, 2*idx+2);
      if(rc.first.first >= lc.first.first + rc.second) return {rc.first, lc.second + rc.second};
      else return {{lc.first.first + rc.second, lc.first.second}, lc.second + rc.second};
    }
  }
  void resize(int k) {
    stok = k;
    st.resize(4*k + 10);
    init(0, k, 0);
  }
  void point_add(int i, int v) {
    u(0, stok, i, 0, v);
  }
  pair<int, int> prefix_mss(int i) {
    return qu(1, i, 0, stok, 0).first;
  }
};
const int MAXN = 250050;
int bit[MAXN];
void not_add(int x, int v) {
  for(;x<MAXN;x+=x&-x) bit[x] += v;
}
int sum(int x) {
  int s=0;
  for(;x;x-=x&-x) s += bit[x];
  return s;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  int l[q+1], r[q+1], c[q+1], k[q+1], a[q+1], b[q+1], ans[q+1], tyy[q+1];
  set<int> add[n+1], sub[n+2], qry[n+1];
  for(int i=1; i<=q; i++) {
    int ty;
    cin >> ty;
    tyy[i] = ty;
    if(ty == 1) {
      cin >> l[i] >> r[i] >> c[i] >> k[i];
      add[l[i]].insert(i);
      sub[r[i]+1].insert(i);
    }
    else if(ty == 2) {
      cin >> l[i] >> r[i] >> k[i];
      k[i] = -k[i];
      c[i] = 0;
      add[l[i]].insert(i);
      sub[r[i]+1].insert(i);
    }
    else {
      cin >> a[i] >> b[i];
      k[i] = 0;
      qry[a[i]].insert(i);
    }
  }
  segtree_basic stb;
  segtree_bruh str;
  stb.resize(q);
  str.resize(q);
  for(int i=1; i<=n; i++) {
    for(int x: add[i]) {
      str.point_add(x, k[x]);
      if(k[x] < 0) not_add(x, k[x]);
      else stb.range_add(x, x, k[x]);
    }
    for(int x: sub[i]) {
      str.point_add(x, -k[x]);
      if(k[x] < 0) not_add(x, -k[x]);
      else stb.range_add(x, x, -k[x]);
    }
    for(int x: qry[i]) {
      pair<int, int> bruh = str.prefix_mss(x);
      if(bruh.first < b[x]) {
        ans[x] = 0; continue;
      }
      int pss = 0;
      if(bruh.second>1) pss= stb.query_sum(1, bruh.second-1);
      int bruh2= sum(x)-sum(bruh.second);
      ans[x] = c[stb.query_firstPSAtLeast(bruh.second, x, b[x] + pss - bruh2)];
    }
  }
  for(int i=1; i<=q; i++) if(tyy[i] == 3) cout << ans[i] << '\n';
  
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11