Submission #1077440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077440		awu	Food Court (JOI21_foodcourt)	C++17	68 / 100	1093 ms	377260 KiB

foodcourt

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii = pair<int, int>;

// const int inf = 1ll << 60;
const int inf = 1 << 30;

template <class T, class _ = decltype(begin(declval<T>()))>
enable_if_t<!is_same_v<T, string>, ostream&> operator<<(ostream& out, T a) {
  string dlm = "";
  out << "{";
  for(auto i : a) {
    out << dlm << i;
    dlm = ", ";
  }
  return out << "}";
}

struct segtree {
  vector<int> t;
  vector<pii> lz;
  segtree(int s) {
    int n = 1;
    while(n < s) n *= 2;
    t.resize(n * 2);
    lz.resize(n * 2);
  }
  void apply(int n, pii upd) {
    lz[n].s += upd.f;
    if(lz[n].s < 0) {
      lz[n].f += lz[n].s;
      lz[n].s = upd.s;
    } else {
      lz[n].s += upd.s;
    }
  }
  void push(int n) {
    t[n] += lz[n].f;
    t[n] = max(t[n], 0ll);
    t[n] += lz[n].s;
    if(n < t.size() / 2) {
      apply(n * 2, lz[n]);
      apply(n * 2 + 1, lz[n]);
    }
    lz[n] = {0, 0};
  }
  void update(int ul, int ur, int v, int n = 1, int tl = 0, int tr = -1) {
    if(tr == -1) tr = t.size() / 2;
    if(ul >= tr || ur <= tl) return;
    if(ul <= tl && ur >= tr) {
      apply(n, {v, 0});
      return;
    }
    push(n);
    int tm = (tl + tr) / 2;
    update(ul, ur, v, n * 2, tl, tm);
    update(ul, ur, v, n * 2 + 1, tm, tr);
    push(n * 2);
    push(n * 2 + 1);
    t[n] = min(t[n * 2], t[n * 2 + 1]);
  }
  int query(int i, int n = 1, int tl = 0, int tr = -1) {
    if(tr == -1) tr = t.size() / 2;
    push(n);
    if(tl + 1 == tr) return t[n];
    int tm = (tl + tr) / 2;
    if(i < tm) return query(i, n * 2, tl, tm);
    return query(i, n * 2 + 1, tm, tr);
  }
};

struct segnode {
  int v;
  signed lc, rc;
  void init();
  void update(int, int, int, int);
  int query(int, int, int, int);
};

const int MAX_Q = 250005;

segnode seg[MAX_Q * 300];
int segsize = 1;

void segnode::init() {
  if(!lc) {
    lc = segsize;
    segsize++;
  }
  if(!rc) {
    rc = segsize;
    segsize++;
  }
}
void segnode::update(int i, int x, int tl, int tr) {
  if(tl + 1 == tr) {
    v = x;
    return;
  }
  signed tm = (tl + tr) / 2;
  if(i < tm) {
    if(!lc) {
      lc = segsize;
      segsize++;
    }
    seg[lc].update(i, x, tl, tm);
    v = seg[lc].v;
    if(rc) v += seg[rc].v;
  } else {
    if(!rc) {
      rc = segsize;
      segsize++;
    }
    seg[rc].update(i, x, tm, tr);
    v = seg[rc].v;
    if(lc) v += seg[lc].v;
  }
}
int segnode::query(int ql, int qr, int tl, int tr) {
  if(ql >= tr || qr <= tl) return 0;
  if(ql <= tl && qr >= tr) return v;
  if(v == 0) return 0;
  int tm = (tl + tr) / 2;
  return (lc ? seg[lc].query(ql, qr, tl, tm) : 0) + (rc ? seg[rc].query(ql, qr, tm, tr) : 0);
}

struct segtree2 {
  int n = 1;
  segtree2(int s) {
    while(n < s) n *= 2;
    segsize = n * 2;
  }
  void update(int l, int r, int v, int time) {
    for(l += n, r += n; l < r; l /= 2, r /= 2) {
      if(l & 1) seg[l++].update(time, v, 0, MAX_Q);
      if(r & 1) seg[--r].update(time, v, 0, MAX_Q);
    }
  }
  int query(int i, int x) { // query earliest time suffix sum of people exceeds x (inclusive)
    vector<signed> nodes;
    for(i += n; i; i /= 2) {
      nodes.push_back(i);
    }
    int tl = 0, tr = MAX_Q;
    while(true) {
      if(tl + 1 == tr) return tl;
      int acc = 0;
      for(auto node : nodes) {
        if(seg[node].rc) acc += seg[seg[node].rc].v;
      }
      vector<signed> newnodes;
      if(acc >= x) {
        for(auto node : nodes) {
          if(seg[node].rc) newnodes.push_back(seg[node].rc);
        }
        tl = (tl + tr) / 2;
      } else {
        x -= acc;
        for(auto node : nodes) {
          if(seg[node].lc) newnodes.push_back(seg[node].lc);
        }
        tr = (tl + tr) / 2;
      }
      swap(nodes, newnodes);
    }
  }
};

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, q; cin >> n >> m >> q;
  segtree st(n);
  segtree2 st2(n);
  vector<int> id(q, -1); // look up c given update time
  for(int i = 0; i < q; i++) {
    int t; cin >> t;
    if(t == 1) {
      int l, r, c, k; cin >> l >> r >> c >> k; l--;
      st.update(l, r, k);
      st2.update(l, r, k, i);
      id[i] = c;
    } else if(t == 2) {
      int l, r, k; cin >> l >> r >> k; l--;
      st.update(l, r, -k);
    } else {
      int a, b; cin >> a >> b; a--; b--;
      int x = st.query(a);
      if(b >= x) cout << 0 << endl;
      else {
        int ri = x - b;
        int lo = st2.query(a, ri);
        cout << id[lo] << "\n" ;
      }
    }
  }
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void segtree::push(long long int)':
foodcourt.cpp:52:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if(n < t.size() / 2) {
      |        ~~^~~~~~~~~~~~~~

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