#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int M, N, P;
array<int, 5> arr[404040];
ll B;
struct segtree {
int cnt[1<<21], mx[1<<21], l[1<<21], r[1<<21], sz[1<<21];
void init(int v, int st, int ed) {
if (st == ed) {
cnt[v] = 0;
mx[v] = l[v] = r[v] = 1;
sz[v] = 1;
return;
}
int mid = (st+ed)/2;
init(2*v, st, mid);
init(2*v+1, mid+1, ed);
cnt[v] = 0;
mx[v] = l[v] = r[v] = ed-st+1;
sz[v] = ed-st+1;
}
void update(int v, int st, int ed, int lt, int rt, int val) {
if (lt > ed || st > rt) return;
if (lt <= st && ed <= rt) {
cnt[v] += val;
if (cnt[v] > 0) mx[v] = l[v] = r[v] = 0;
else if (st == ed) mx[v] = l[v] = r[v] = 1;
else {
if (mx[2*v] == sz[2*v]) l[v] = l[2*v+1] + sz[2*v];
else l[v] = l[2*v];
if (mx[2*v+1] == sz[2*v+1]) r[v] = r[2*v] + sz[2*v+1];
else r[v] = r[2*v+1];
mx[v] = max(mx[2*v], mx[2*v+1]);
mx[v] = max(mx[v], r[2*v]+l[2*v+1]);
}
return;
}
int mid = (st+ed)/2;
update(2*v, st, mid, lt, rt, val);
update(2*v+1, mid+1, ed, lt, rt, val);
if (cnt[v] > 0) mx[v] = l[v] = r[v] = 0;
else {
if (mx[2*v] == sz[2*v]) l[v] = l[2*v+1] + sz[2*v];
else l[v] = l[2*v];
if (mx[2*v+1] == sz[2*v+1]) r[v] = r[2*v] + sz[2*v+1];
else r[v] = r[2*v+1];
mx[v] = max(mx[2*v], mx[2*v+1]);
mx[v] = max(mx[v], r[2*v]+l[2*v+1]);
}
}
} seg;
vector<array<int, 3>> add[1010101], rem[1010101];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> M >> N;
cin >> B >> P;
for (int i = 1; i <= P; i++) {
cin >> arr[i][0] >> arr[i][1] >> arr[i][2] >> arr[i][3] >> arr[i][4];
}
seg.init(1, 1, N);
for (int i = 1; i <= P; i++) {
add[arr[i][0]].push_back({arr[i][1], arr[i][3], +1});
rem[arr[i][2]+1].push_back({arr[i][1], arr[i][3], -1});
}
int p = 1, q = 0, ans = 0;
while (q <= M) {
cout << p << " " << q << " " << seg.mx[1] << "\n";
if (seg.mx[1] >= q-p+1) {
ans = max(ans, q-p+1);
q++;
for (auto &[l, r, w] : add[q]) seg.update(1, 1, N, l, r, w);
}
else {
ans = max(ans, seg.mx[1]);
p++;
for (auto &[l, r, w] : rem[p]) seg.update(1, 1, N, l, r, w);
}
}
cout << ans << "\n";
return 0;
}
Compilation message
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:83:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | for (auto &[l, r, w] : add[q]) seg.update(1, 1, N, l, r, w);
| ^
pyramid_base.cpp:88:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for (auto &[l, r, w] : rem[p]) seg.update(1, 1, N, l, r, w);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
59988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
59996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
59996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
60408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
63352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
383 ms |
126036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
347 ms |
129160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
60760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
64676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
407 ms |
131924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
410 ms |
132512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
413 ms |
132824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
829 ms |
146592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
989 ms |
155712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1117 ms |
165092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
