#include <cstdio>
#include <algorithm>
#include <vector>
#define m (s+e)/2
using namespace std;
typedef pair<long long, int> ii;
int N, M, Q, T[250001], L[250001], R[250001], C[250001], ans[250001];
long long K[250001];
struct seg {
int s, e;
long long lazy, v;
seg *l, *r;
seg(int _s, int _e) {
s = _s, e = _e;
lazy = 0;
v = 0;
if (s != e) {
l = new seg(s, m);
r = new seg(m + 1, e);
}
}
void prop() {
if (lazy) {
v += lazy;
if (s != e) {
l -> lazy += lazy;
r -> lazy += lazy;
}
lazy = 0;
}
}
void update(int a, int b, long long dv) {
if (s != a || e != b) {
if (a > m) r -> update(a, b, dv);
else if (b <= m) l -> update(a, b, dv);
else l -> update(a, m, dv), r -> update(m + 1, b, dv);
l -> prop(), r -> prop();
v = min(l -> v, r -> v);
} else lazy += dv;
}
long long query(int a, int b) {
prop();
if (s == a && e == b) return v;
if (a > m) return r -> query(a, b);
if (b <= m) return l -> query(a, b);
return min(l -> query(a, m), r -> query(m + 1, b));
}
int descend(int i, long long k) {
prop();
if (s == e) return s;
if (m < i && r -> lazy + r -> v < k) return r -> descend(i, k);
return l -> descend(i, k);
}
} *r1, *r2;
struct dnc {
int s, e;
vector<int> ops;
dnc *l, *r;
dnc(int _s, int _e) {
s = _s, e = _e;
if (s != e) {
l = new dnc(s, m);
r = new dnc(m + 1, e);
}
}
void update(int x, int i) {
if (s != e) {
if (x > m) r -> update(x, i);
else l -> update(x, i);
} else ops.push_back(i);
}
void query() {
for (int i: ops) {
if (i < 0 && T[-i] == 1) r1 -> update(-i, Q, -K[-i]), r2 -> update(-i, Q, -K[-i]);
else if (i < 0 && T[-i] == 2) r1 -> update(-i, Q, K[-i]);
else if (T[i] == 3) {
long long curr = r1 -> query(i, i) - r1 -> query(0, i);
int l = r2 -> descend(i, r2 -> query(i, i) - curr + K[i]);
if (l == i) ans[i] = 0;
else ans[i] = C[l + 1];
} else if (T[i] == 1) r1 -> update(i, Q, K[i]), r2 -> update(i, Q, K[i]);
else r1 -> update(i, Q, -K[i]);
}
if (s != e) {
l -> query();
r -> query();
}
}
} *dc;
int main() {
scanf("%d %d %d", &N, &M, &Q);
r1 = new seg(0, Q);
r2 = new seg(0, Q);
dc = new dnc(1, N);
for (int i = 1; i <= Q; ++i) {
scanf("%d", &T[i]);
if (T[i] == 1) scanf("%d %d %d %lld", &L[i], &R[i], &C[i], &K[i]);
else if (T[i] == 2) scanf("%d %d %lld", &L[i], &R[i], &K[i]);
else scanf("%d %lld", &L[i], &K[i]), R[i] = L[i];
dc -> update(L[i], i);
if (T[i] != 3) dc -> update(R[i], -i);
}
dc -> query();
for (int i = 1; i <= Q; ++i) {
if (T[i] == 3) printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d %d %d", &N, &M, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d", &T[i]);
| ~~~~~^~~~~~~~~~~~~
foodcourt.cpp:97:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | if (T[i] == 1) scanf("%d %d %d %lld", &L[i], &R[i], &C[i], &K[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:98:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | else if (T[i] == 2) scanf("%d %d %lld", &L[i], &R[i], &K[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:99:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | else scanf("%d %lld", &L[i], &K[i]), R[i] = L[i];
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
219 ms |
24096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
83600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
22320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
