Submission #971444

#	Time	Username	Problem	Language	Result	Execution time	Memory
971444		abczz	Food Court (JOI21_foodcourt)	C++14	100 / 100	802 ms	102736 KiB

foodcourt

#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

ll n, m, q, t, a, b, c, d, F[250000], T[250000];
vector <array<ll, 2> > Q[250000];
vector <array<ll, 2> > X[250000];

struct SegTree{
  vector <ll> st{vector<ll>(1e6, 0)};
  vector <array<ll, 2> > lazy{vector<array<ll, 2> >(1e6, {0, 0})};
  array<ll, 2> merge(array<ll, 2> A, array<ll, 2> B) {
    return {max(A[0]+B[1], B[0]), A[1]+B[1]};
  }
  void push(ll id) {
    st[id*2] = max(lazy[id][0], st[id*2]+lazy[id][1]);
    st[id*2+1] = max(lazy[id][0], st[id*2+1]+lazy[id][1]);
    lazy[id*2] = merge(lazy[id*2], lazy[id]);
    lazy[id*2+1] = merge(lazy[id*2+1], lazy[id]);
    lazy[id] = {0, 0};
  }
  void update_max_add(ll id, ll l, ll r, ll ql, ll qr, array<ll, 2> w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st[id] = max(w[0], st[id]+w[1]);
      lazy[id] = merge(lazy[id], w);
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    update_max_add(id*2, l, mid, ql, qr, w);
    update_max_add(id*2+1, mid+1, r, ql, qr, w);
    st[id] = st[id*2] + st[id*2+1];
  }
  ll query(ll id, ll l, ll r, ll q) {
    if (l == r) return st[id];
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) return query(id*2, l, mid, q);
    else return query(id*2+1, mid+1, r, q);
  }
  ll solve(ll id, ll l, ll r, ll w) {
    //cout << st[id] << " " << l << " " << r << " " << w << endl;
    if (l == r) return T[l];
    push(id);
    ll mid = (l+r)/2;
    if (st[id*2] > w) return solve(id*2, l, mid, w);
    else return solve(id*2+1, mid+1, r, w-st[id*2]);
  }
} ST, CAP, SWP;
int main() {
  cin >> n >> m >> q;
  for (int i=0; i<q; ++i) {
    F[i] = 1e18;
    cin >> t;
    if (t == 1) {
      cin >> a >> b >> c >> d;
      --a, --b;
      X[a].push_back({i, d});
      T[i] = c;
      if (b != n-1) X[b+1].push_back({i, -d});
      ST.update_max_add(1, 0, n-1, a, b, {0, d});
      CAP.update_max_add(1, 0, n-1, a, b, {0, d});
    }
    else if (t == 2) {
      cin >> a >> b >> c;
      --a, --b;
      ST.update_max_add(1, 0, n-1, a, b, {0, -c});
    }
    else {
      cin >> a >> b;
      --a, --b;
      ll cap = CAP.query(1, 0, n-1, a), res = ST.query(1, 0, n-1, a);
      if (b-res >= 0) F[i] = 0;
      else Q[a].push_back({i, b+cap-res});
    }
  }
  for (int i=0; i<n; ++i) {
    for (auto [u, w] : X[i]) {
      SWP.update_max_add(1, 0, q-1, u, u, {0, w});
    }
    for (auto [id, u] : Q[i]) {
      F[id] = SWP.solve(1, 0, q-1, u);
    }
  }
  for (int i=0; i<q; ++i) {
    if (F[i] == 1e18) continue;
    cout << F[i] << '\n';
  }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto [u, w] : X[i]) {
      |               ^
foodcourt.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for (auto [id, u] : Q[i]) {
      |               ^

• 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