#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 250000, N_ = 1 << 18, INF = 0x3f3f3f3f;
int n_;
array<LL, 2> st1[N_ * 2];
array<LL, 2> join(array<LL, 2> a, array<LL, 2> b) {
return { a[0] + b[0], max(a[1] + b[0], b[1]) };
}
void update1(int i, int x) {
i |= n_;
st1[i][0] = x;
st1[i][1] = max(0, x);
while (i >>= 1)
st1[i] = join(st1[i << 1 | 0], st1[i << 1 | 1]);
}
LL query1(int l, int r) {
vector<int> ll, rr;
array<LL, 2> v = { 0, 0 };
for (l |= n_, r |= n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
ll.push_back(l++);
if ((r & 1) == 0)
rr.push_back(r--);
}
for (int i : ll)
v = join(v, st1[i]);
reverse(rr.begin(), rr.end());
for (int i : rr)
v = join(v, st1[i]);
return v[1];
}
LL st2[N_ * 2], ll[N_ * 2];
void update2(int i, int x) {
i |= n_;
ll[i] = st2[i] = x;
while (i >>= 1) {
st2[i] = st2[i << 1 | 0] + st2[i << 1 | 1];
ll[i] = ll[i << 1 | 0];
}
}
LL query2(int l, int r) {
LL sum = 0;
for (l |= n_, r |= n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
sum += st2[l++];
if ((r & 1) == 0)
sum += st2[r--];
}
return sum;
}
int query3(LL x) {
int i = 1;
while (i < n_) {
if (st2[i << 1 | 0] + ll[i << 1 | 1] < x) {
x -= st2[i << 1 | 0];
i = i << 1 | 1;
} else
i = i << 1 | 0;
}
return i ^ n_;
}
vector<pair<int, int>> uu[N], qq[N];
void run() {
static int cc[N], ans[N];
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
n_ = 1;
while (n_ < q)
n_ <<= 1;
for (int h = 0; h < q; h++) {
int t;
scanf("%d", &t);
if (t == 1) {
int l, r, k;
scanf("%d%d%d%d", &l, &r, &cc[h], &k), l--;
uu[l].push_back({ h << 1 | 0, k });
uu[r].push_back({ h << 1 | 0, 0 });
} else if (t == 2) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k), l--;
uu[l].push_back({ h << 1 | 1, -k });
uu[r].push_back({ h << 1 | 1, 0 });
} else {
int i, k;
scanf("%d%d", &i, &k), i--;
qq[i].push_back({ h, k });
}
}
memset(ans, -1, q * sizeof * ans);
for (int i = 0; i < n; i++) {
for (auto [h2, k] : uu[i]) {
int h = h2 >> 1;
update1(h, k);
if ((h2 & 1) == 0)
update2(h, k);
}
for (auto [h, k] : qq[i]) {
LL x = query1(0, h);
ans[h] = x < k ? 0 : cc[query3(query2(0, h) - x + k - 1) + 1];
}
}
for (int h = 0; h < q; h++)
if (ans[h] != -1)
printf("%d\n", ans[h]);
}
int main() {
run();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void run()':
foodcourt.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d%d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
foodcourt.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d%d%d%d", &l, &r, &cc[h], &k), l--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d%d%d", &l, &r, &k), l--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d%d", &i, &k), i--;
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
18864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
345 ms |
36356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
18288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
