#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = (1 << 18);
#define cerr if (false) cout
struct node {
ll sum = 0;
ll pre = 0;
};
node tr[2 * N];
node combine(node a, node b) {
node res;
res.sum = a.sum + b.sum;
res.pre = min(a.pre, a.sum + b.pre);
return res;
}
void update(int pos, ll val) {
cerr << "upd: " << pos << ' ' << val << '\n';
tr[pos += N] = {val, min(0ll, val)};
for (pos >>= 1; pos; pos >>= 1)
tr[pos] = combine(tr[2 * pos], tr[2 * pos + 1]);
cerr << "tree: " << tr[1].sum << ' ' << tr[1].pre << '\n';
}
node get(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
if (r < ql || l > qr)
return node();
if (ql <= l && r <= qr)
return tr[v];
int m = (l + r) / 2;
return combine(get(ql, qr, l, m, 2 * v), get(ql, qr, m + 1, r, 2 * v + 1));
}
ll cnt[2 * N];
void add(int v, ll a) {
for (cnt[v += N] += a; v > 1; v >>= 1)
cnt[v >> 1] = cnt[v] + cnt[v^1];
}
ll count(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
if (r < ql || l > qr)
return 0;
if (ql <= l && r <= qr)
return cnt[v];
int m = (l + r) / 2;
return count(ql, qr, l, m, 2 * v) + count(ql, qr, m + 1, r, 2 * v + 1);
}
int n, m, q;
vector<pair<int, int>> join[N][2];
vector<pair<int, int>> leave[N][2];
vector<pair<int, int>> service[N];
map<int, int> timeToGroup;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int t = 1; t <= q; t++) {
int type;
cin >> type;
if (type == 1) {
int l, r, k, c;
cin >> l >> r >> c >> k;
timeToGroup[t] = c;
join[l][0].push_back({t, k});
join[r][1].push_back({t, k});
}
if (type == 2) {
int l, r, k;
cin >> l >> r >> k;
leave[l][0].push_back({t, k});
leave[r][1].push_back({t, k});
}
if (type == 3) {
int a, b;
cin >> a >> b;
service[a].push_back({t, b});
}
}
vector<int> res(q + 1, -2);
for (int i = 1; i <= n; i++) {
for (auto o : join[i][0]) {
int t = o.first, k = o.second;
update(t, +k);
add(t, +k);
}
for (auto o : leave[i][0]) {
int t = o.first, k = o.second;
update(t, -k);
}
for (auto [t, b] : service[i]) {
int num = get(1, t).sum - get(1, t).pre;
// cerr << "service: " << t << ' ' << b << '\n';
// cerr << get(1, t).sum << '\n';
if (num < b) {
res[t] = 0;
continue;
}
int l = 0, r = t + 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (count(m, t) >= b)
l = m;
else
r = m;
}
res[t] = timeToGroup[l];
}
for (auto o : join[i][1]) {
int t = o.first, k = o.second;
update(t, 0);
add(t, -k);
}
for (auto o : leave[i][1]) {
int t = o.first, k = o.second;
update(t, 0);
}
}
for (int i = 1; i <= q; i++) {
if (res[i] != -2)
cout << res[i] << '\n';
}
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:122:30: warning: unused variable 'k' [-Wunused-variable]
122 | int t = o.first, k = o.second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
39508 KB |
Output is correct |
| 2 |
Correct |
71 ms |
40272 KB |
Output is correct |
| 3 |
Correct |
66 ms |
39508 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
39504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
34324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
31960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
