Submission #1037124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037124		juicy	Food Court (JOI21_foodcourt)	C++17	100 / 100	230 ms	45908 KiB

foodcourt

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 25e4 + 5;
 
int n, m, q;
int c[N], res[N];
long long cnt[4 * N];
array<long long, 2> s[4 * N];
vector<pair<long long, int>> Queries[N];
vector<array<int, 3>> events[N];
 
array<long long, 2> operator + (const array<long long, 2> &lt, const array<long long, 2> &rt) {
  return {max(lt[0] + rt[1], rt[0]), lt[1] + rt[1]};
}
 
template<class T>
void upd(int i, T x, T *s, int id = 1, int l = 1, int r = q) {
  if (l == r) {
    s[id] = x;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, s, id * 2, l, md);
  } else {
    upd(i, x, s, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
}
 
template<class T>
T qry(int i, T *s, int id = 1, int l = 1, int r = q) {
  if (l == r) {
    return s[id];
  }
  int md = (l + r) / 2;
  if (i <= md) {
    return qry(i, s, id * 2, l, md);
  }
  return s[id * 2] + qry(i, s, id * 2 + 1, md + 1, r);
}
 
long long walk(long long k, int id = 1, int l = 1, int r = q) {
  if (l == r) {
    return c[l];
  }
  int md = (l + r) / 2;
  if (k > cnt[id * 2]) {
    return walk(k - cnt[id * 2], id * 2 + 1, md + 1, r);
  }
  return walk(k, id * 2, l, md);
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n >> m >> q;
  for (int i = 1; i <= q; ++i) {
    int t; cin >> t;
    if (t == 1) {
      int l, r, k; cin >> l >> r >> c[i] >> k;
      events[l].push_back({i, k, 1});
      events[r + 1].push_back({i, 0, 1});
    } else if (t == 2) {
      int l, r, k; cin >> l >> r >> k;
      events[l].push_back({i, -k, 2});
      events[r + 1].push_back({i, 0, 2});
    } else {
      int p; long long x; cin >> p >> x;
      Queries[p].push_back({x, i});
    }
  }  
  for (int i = 1; i <= n; ++i) {
    for (auto [p, k, t] : events[i]) {
      upd(p, array<long long, 2>{max(0, k), k}, s);
      if (t == 1) {
        upd(p, (long long) k, cnt);
      }
    }
    for (auto [x, id] : Queries[i]) {
      auto dat = qry(id, s);
      if (dat[0] >= x) {
        res[id] = walk(qry(id, cnt) - dat[0] + x) + 1;
      } else {
        res[id] = 1;
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (res[i]) {
      cout << res[i] - 1 << "\n";
    }
  } 
  return 0;
}

• 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