Submission #585277

#	Time	Username	Problem	Language	Result	Execution time	Memory
585277		Soumya1	Food Court (JOI21_foodcourt)	C++17	68 / 100	1094 ms	38604 KiB

foodcourt

#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 250005;
struct Node {
  long long sum, max_suf, pos_sum;
  Node() { sum = max_suf = pos_sum = 0; }
} t[4 * mxN];
void propagate(int x, int lx, int rx) {
  if (lx == rx) return;
  t[x << 1].sum += t[x].sum;
  t[x << 1 | 1].sum += t[x].sum;
  t[x << 1].max_suf = max({t[x].sum + t[x << 1].max_suf, t[x].max_suf, 0LL});
  t[x << 1 | 1].max_suf = max({t[x].sum + t[x << 1 | 1].max_suf, t[x].max_suf, 0LL});
  t[x << 1].pos_sum += t[x].pos_sum;
  t[x << 1 | 1].pos_sum += t[x].pos_sum;
  t[x] = Node();
}
void update(int x, int lx, int rx, int l, int r, int k) {
  if (t[x].sum != 0 || t[x].max_suf != 0 || t[x].pos_sum != 0) propagate(x, lx, rx);
  if (l > rx || lx > r) return;
  if (l <= lx && r >= rx) {
    t[x].sum += k;
    t[x].pos_sum += max(k, 0);
    t[x].max_suf = max(t[x].max_suf + k, 0LL);
    return;
  }
  int mx = (lx + rx) >> 1;
  update(x << 1, lx, mx, l, r, k);
  update(x << 1 | 1, mx + 1, rx, l, r, k);
}
Node query(int x, int lx, int rx, int i) {
  if (t[x].sum != 0 || t[x].max_suf != 0 || t[x].pos_sum != 0) propagate(x, lx, rx);
  if (lx == rx) return t[x];
  int mx = (lx + rx) >> 1;
  if (i <= mx) return query(x << 1, lx, mx, i);
  return query(x << 1 | 1, mx + 1, rx, i);
}
void testCase() {
  int n, m, q;
  cin >> n >> m >> q;
  vector<pair<int, long long>> Q;
  vector<tuple<int, int, int, int>> updates;
  updates.push_back({1, n, 0, 0});
  for (int i = 1; i <= q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int l, r, c, k;
      cin >> l >> r >> c >> k;
      update(1, 1, n, l, r, k);
      updates.push_back({l, r, k, c});
    } else if (t == 2) {
      int l, r, k;
      cin >> l >> r >> k;
      update(1, 1, n, l, r, -k);
    } else {
      int a;
      long long b;
      cin >> a >> b;
      auto x = query(1, 1, n, a);
      long long rem = x.max_suf;
      long long added = x.pos_sum;
      if (rem >= b) {
        Q.push_back({a, added - rem + b});
      } else {
        Q.push_back({a, 0});
      }
    }
  }
  q = Q.size();
  vector<int> lo(q), hi(q);
  for (int i = 0; i < q; i++) {
    lo[i] = 0, hi[i] = max(0, (int) updates.size() - 1);
  }
  for (int iter = 0; iter < 20; iter++) {
    for (int i = 0; i <= 4 * n; i++) t[i] = Node();
    vector<tuple<int, long long, int>> qq[updates.size()];
    for (int i = 0; i < q; i++) {
      qq[(lo[i] + hi[i]) / 2].push_back({Q[i].first, Q[i].second, i});
    }
    for (int i = 0; i < updates.size(); i++) {
      auto [l, r, k, c] = updates[i];
      update(1, 1, n, l, r, k);
      for (auto [a, b, id] : qq[i]) {
        auto x = query(1, 1, n, a);
        if (x.sum >= b) hi[id] = i;
        else lo[id] = i + 1; 
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << get<3> (updates[lo[i]]) << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
}

Compilation message (stderr)

foodcourt.cpp: In function 'void testCase()':
foodcourt.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < updates.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

• 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