| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1138409 | duckindog | Food Court (JOI21_foodcourt) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 250'000 + 10;
int n, m, q;
namespace IT1 {
vector<long long> lazy[N << 2];
void shrink(int s) {
while (lazy[s].size() >= 2) {
if (lazy[s].back() <= 0) {
lazy[s].end()[-2] += lazy[s].back();
lazy[s].pop_back();
continue;
}
if (lazy[s].back() > 0 && lazy[s].end()[-2] >= 0) {
lazy[s].end()[-2] += lazy[s].back();
lazy[s].pop_back();
continue;
}
break;
}
if (lazy[s].size() && lazy[s].back() == 0) lazy[s].pop_back();
}
void push(int s) {
if (!lazy[s].size()) return;
for (const auto& x : lazy[s]) {
lazy[s << 1].push_back(x); lazy[s << 1 | 1].push_back(x);
shrink(s << 1); shrink(s << 1 | 1);
}
lazy[s].clear();
}
void update(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
lazy[s].push_back(x);
shrink(s);
return;
}
push(s);
int mid = (l + r) >> 1;
update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
}
long long query(int s, int l, int r, int p) {
if (p < l || p > r) return 0;
if (l == r) return lazy[s].size() ? lazy[s].back() : 0;
push(s);
int mid = (l + r) >> 1;
return max(query(s << 1, l, mid, p), query(s << 1 | 1, mid + 1, r, p));
}
}
namespace IT2 {
long long f[N << 2];
void update(int s, int l, int r, int p, int x) {
if (p < l || p > r) return;
if (l == r) {
f[s] = max(x, 0);
return;
}
int mid = (l + r) >> 1;
update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
f[s] = f[s << 1] + f[s << 1 | 1];
}
int query(int s, int l, int r, int p) {
if (p < l || p > r) return 0;
if (l == r) return f[s];
int mid = (l + r) >> 1;
return query(s << 1, l, mid, p) + query(s << 1 | 1, mid + 1, r, p);
}
vector<tuple<int, int, int>> segments;
void collect(int s, int l, int r, int u, int v) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
segments.emplace_back(s, l, r);
return;
}
int mid = (l + r) >> 1;
collect(s << 1, l, mid, u, v); collect(s << 1 | 1, mid + 1, r, u, v);
}
int walk(int s, int l, int r, long long k) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (f[s << 1 | 1] <= k) return walk(s << 1, l, mid, k - f[s << 1 | 1]);
return walk(s << 1 | 1, mid + 1, r, k);
}
int find(int l, int r, long long k) {
segments.clear();
collect(1, 1, q, l, r);
reverse(segments.begin(), segments.end());
for (const auto& [s, l, r] : segments) {
if (f[s] <= k) k -= f[s];
else return walk(s, l, r, k);
}
assert(false);
}
}
vector<tuple<int, int, int>> saveUpdate[N];
vector<pair<int, long long>> saveQuery[N];
int fromGroup[N];
int answer[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
memset(answer, -1, sizeof answer);
for (int i = 1; i <= q; ++i) {
int type; cin >> type;
if (type == 1) {
int l, r, c, k; cin >> l >> r >> c >> k;
IT1::update(1, 1, n, l, r, k);
saveUpdate[l].emplace_back(1, i, k);
saveUpdate[r + 1].emplace_back(0, i, k);
fromGroup[i] = c;
}
if (type == 2) {
int l, r, k; cin >> l >> r >> k;
IT1::update(1, 1, n, l, r, -k);
}
if (type == 3) {
int p; cin >> p;
long long k; cin >> k;
answer[i] = IT1::query(1, 1, n, p);
saveQuery[p].push_back({i, k});
}
}
for (int i = 1; i <= n; ++i) {
for (const auto& [type, pos, k] : saveUpdate[i])
IT2::update(1, 1, q, pos, type * k);
for (const auto& [idx, k] : saveQuery[i])
answer[idx] = (answer[idx] < k ? 0 : fromGroup[IT2::find(1, idx, answer[idx] - k)]);
}
for (int i = 1; i <= q; ++i)
if (answer[i] != -1) cout << answer[i] << "\n";
}