#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
const int INF = 1e9 + 7;
struct Point {
int x, y;
};
struct Node {
int len, mn, l, r, val, lval, rval, add;
};
Node tree[MAXN * 4];
void calc(int v) {
tree[v].len = tree[v * 2 + 1].len + tree[v * 2 + 2].len;
tree[v].mn = min(tree[v * 2 + 1].mn, tree[v * 2 + 2].mn);
tree[v].lval = tree[v * 2 + 1].lval;
tree[v].rval = tree[v * 2 + 2].rval;
if (tree[v * 2 + 1].l == tree[v * 2 + 1].len && tree[v * 2 + 1].lval == tree[v * 2 + 2].lval) {
tree[v].l = tree[v * 2 + 1].len + tree[v * 2 + 2].l;
}
else {
tree[v].l = tree[v * 2 + 1].l;
}
if (tree[v * 2 + 2].r == tree[v * 2 + 2].len && tree[v * 2 + 1].rval == tree[v * 2 + 2].rval) {
tree[v].r = tree[v * 2 + 2].len + tree[v * 2 + 1].r;
}
else {
tree[v].r = tree[v * 2 + 2].r;
}
tree[v].val = -INF;
if (tree[v * 2 + 1].mn == tree[v].mn) tree[v].val = max(tree[v].val, tree[v * 2 + 1].val);
if (tree[v * 2 + 2].mn == tree[v].mn) tree[v].val = max(tree[v].val, tree[v * 2 + 2].val);
if (tree[v * 2 + 1].rval == tree[v].mn && tree[v * 2 + 2].lval == tree[v].mn) {
tree[v].val = max(tree[v].val, tree[v * 2 + 1].r + tree[v * 2 + 2].l);
}
}
void push(int v) {
tree[v * 2 + 1].add += tree[v].add;
tree[v * 2 + 1].mn += tree[v].add;
tree[v * 2 + 1].lval += tree[v].add;
tree[v * 2 + 1].rval += tree[v].add;
tree[v * 2 + 2].add += tree[v].add;
tree[v * 2 + 2].mn += tree[v].add;
tree[v * 2 + 2].lval += tree[v].add;
tree[v * 2 + 2].rval += tree[v].add;
tree[v].add = 0;
}
void upd(int v, int tl, int tr, int l, int r, int x) {
if (tr < l || r < tl) return;
if (l <= tl && tr <= r) {
tree[v].add += x;
tree[v].lval += x;
tree[v].rval += x;
tree[v].mn += x;
return;
}
int tm = (tl + tr) / 2;
push(v);
upd(v * 2 + 1, tl, tm, l, r, x);
upd(v * 2 + 2, tm + 1, tr, l, r, x);
calc(v);
}
vector <pair <int, int> > add_sc[MAXN];
vector <pair <int, int> > del_sc[MAXN];
bool check(int lx, int rx) {
return (tree[0].mn == 0 && tree[0].val >= rx - lx + 1);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v].len = 1;
tree[v].mn = 0;
tree[v].l = 1;
tree[v].r = 1;
tree[v].val = 1;
tree[v].lval = 0;
tree[v].rval = 0;
tree[v].add = 0;
return;
}
int tm = (tl + tr) / 2;
build(v * 2 + 1, tl, tm);
build(v * 2 + 2, tm + 1, tr);
calc(v);
}
void myadd(int r, int n) {
for (pair <int, int> e : add_sc[r]) {
upd(0, 1, n, e.first, e.second, 1);
}
}
void mydel(int l, int n) {
for (pair <int, int> e : del_sc[l]) {
upd(0, 1, n, e.first, e.second, -1);
}
}
signed main() {
ios_base::sync_with_stdio(false);
int m, n;
cin >> m >> n;
int b;
cin >> b;
if (b != 0) return 1;
int p;
cin >> p;
vector <pair <Point, Point> > a(p);
for (int i = 0; i < p; ++i) {
cin >> a[i].first.x >> a[i].first.y >> a[i].second.x >> a[i].second.y;
int c;
cin >> c;
}
for (int i = 0; i < p; ++i) {
add_sc[a[i].first.x].push_back({a[i].first.y, a[i].second.y});
del_sc[a[i].second.x + 1].push_back({a[i].first.y, a[i].second.y});
}
build(0, 1, n);
int ans = 0;
int rx = 1;
myadd(1, n);
for (int lx = 1; lx <= m; ++lx) {
if (rx < lx) {
for (int i = rx + 1; i <= lx; ++i) myadd(i, n);
rx = lx;
}
mydel(lx, n);
while (rx <= m && check(lx, rx)) {
++rx;
myadd(rx, n);
}
ans = max(ans, rx - lx);
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
47360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
48384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
55680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
113120 KB |
Output is correct |
| 2 |
Correct |
95 ms |
113144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
113016 KB |
Output is correct |
| 2 |
Correct |
89 ms |
113212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
47360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
47360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
47360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
47360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
47352 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
706 ms |
133400 KB |
Output is correct |
| 2 |
Correct |
384 ms |
70136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
916 ms |
142972 KB |
Output is correct |
| 2 |
Correct |
904 ms |
139100 KB |
Output is correct |
| 3 |
Correct |
576 ms |
131912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1213 ms |
151932 KB |
Output is correct |
| 2 |
Correct |
1387 ms |
149236 KB |
Output is correct |
| 3 |
Correct |
1397 ms |
149280 KB |
Output is correct |
| 4 |
Correct |
1210 ms |
147168 KB |
Output is correct |
| 5 |
Correct |
861 ms |
141968 KB |
Output is correct |
