Submission #1170785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170785		dombly	Food Court (JOI21_foodcourt)	C++20	100 / 100	367 ms	36356 KiB

foodcourt

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 250005;
int n, m, q;
int ec[maxn];
vector<tuple<long long, int, int>> ev[maxn];

pair<long long, int> tree[maxn << 2];
long long lazy[maxn << 2];

void build(int ind = 1, int l = 1, int r = q) {
  if (l == r) {
    tree[ind] = make_pair(0, l);
    return;
  }
  int mid = (l + r) >> 1;
  build(ind << 1, l, mid);
  build(ind << 1 | 1, mid + 1, r);
  tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
}

void down(int ind, int l, int r) {
  tree[ind].first += lazy[ind];
  if (l != r) {
    lazy[ind << 1] += lazy[ind];
    lazy[ind << 1 | 1] += lazy[ind];
  }
  lazy[ind] = 0;
}

void update(int x, int y, long long val, int ind = 1, int l = 1, int r = q) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return;
  if (x <= l and r <= y) {
    lazy[ind] = val;
    down(ind, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update(x, y, val, ind << 1, l, mid);
  update(x, y, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
}

pair<long long, int> get(int x, int y, int ind = 1, int l = 1, int r = q) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return make_pair(1e9, -1);
  if (x <= l and r <= y) return tree[ind];
  int mid = (l + r) >> 1;
  return min(get(x, y, ind << 1, l, mid), get(x, y, ind << 1 | 1, mid + 1, r));
}

struct fenwick_tree {
  long long bit[maxn];
  
  void update(int i, long long val) {
    for (; i < maxn; i += i & (-i)) {
      bit[i] += val;
    }
  }  
  
  long long get(int i) {
    long long ans = 0;
    for (; i > 0; i -= i & (-i)) {
      ans += bit[i];
    }
    return ans;
  }
  
  long long get(int l, int r) {
    return l > r ? 0 : get(r) - get(l - 1);
  }
  
  int lower_bound(long long v) {
    long long sum = 0;
    int pos = 0;
    for (int i = 20; i >= 0; i--) {
      if (pos + (1 << i) < maxn and sum + bit[pos + (1 << i)] < v) {
        sum += bit[pos + (1 << i)];
        pos += (1 << i);
      }
    }
    return pos + 1;
  }
} ft[2];

void solve() {
  cin >> n >> m >> q;
  for (int i = 1; i <= q; ++i) {
    int op; cin >> op;
    if (op == 1) {
      int l, r, c, k; cin >> l >> r >> c >> k;
      ev[l].emplace_back(k, 1, i);
      if (r < n) {
        ev[r + 1].emplace_back(-k, 1, i);
      }
      ec[i] = c;
    } else if (op == 2) {
      int l, r, k; cin >> l >> r >> k;
      ev[l].emplace_back(-k, 2, i);
      if (r < n) {
        ev[r + 1].emplace_back(k, 2, i);
      }
    } else {
      int a; long long b; cin >> a >> b;
      ev[a].emplace_back(b, 3, i);
    }
  }
  build();
  vector<pair<int, int>> res;
  for (int i = 1; i <= n; ++i) {
    for (auto [v, type, id] : ev[i]) {
      if (type < 3) {
        update(id, q, v);     
        if (type == 1) ft[0].update(id, v);
        else ft[1].update(id, -v);
      }
    }
    for (auto [v, type, id] : ev[i]) {
      if (type == 3) {
        auto [offset, p] = get(1, id);
        if (offset >= 0) {
          p = 0;
        }
        v += ft[1].get(p + 1, id);
        if (ft[0].get(p + 1, id) < v) {
          res.emplace_back(id, 0);
        } else {
          int oe = ft[0].lower_bound(ft[0].get(p) + v);
          res.emplace_back(id, ec[oe]);
        }
      }
    }
  }
  sort(res.begin(), res.end());
  for (auto i:res) {
    cout << i.second << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  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