#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 10;
int n, m, p;
int budget;
vector <int> x, y, x2, y2, cost;
struct Node {
int pref, suff, mx;
};
Node t[N * 4];
int lazy[N * 4];
struct SegmentTree {
int v;
int tl;
int tr;
SegmentTree(int n) {
v = 1;
tl = 1;
tr = n;
build(v, tl, tr);
};
void add(int l, int r, int incVal) {
update(v, tl, tr, l, r, incVal);
}
int get() {
return t[v].mx;
}
private:
void update(int v, int tl, int tr, int l, int r, int incVal) {
if (l > r) {
return;
}
if (tl == l && tr == r) {
lazy[v] += incVal;
combine(v, tl, tr);
return;
}
int tm = tl + tr >> 1;
update(v << 1, tl, tm, l, min(r, tm), incVal);
update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, incVal);
combine(v, tl, tr);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
combine(v, tl, tr);
return;
}
int tm = tl + tr >> 1;
build(v << 1, tl, tm);
build(v << 1 | 1, tm + 1, tr);
combine(v, tl, tr);
}
void combine(int v, int tl, int tr) {
if (lazy[v]) {
t[v].mx = 0;
t[v].pref = 0;
t[v].suff = 0;
return;
}
if (tl == tr) {
t[v].mx = 1;
t[v].pref = 1;
t[v].suff = 1;
return;
}
int l = v << 1;
int r = v << 1 | 1;
int tm = tl + tr >> 1;
int szLeft = tm - tl + 1;
int szRight = tr - tm;
t[v].mx = max(t[l].mx, t[r].mx);
if (t[l].pref == szLeft) {
t[v].pref = t[l].pref + t[r].pref;
}
else {
t[v].pref = t[l].pref;
}
if (t[r].suff == szRight) {
t[v].suff = t[l].suff + t[r].suff;
}
else {
t[v].suff = t[r].suff;
}
t[v].mx = max(t[v].mx, t[v].pref);
t[v].mx = max(t[v].mx, t[v].suff);
}
};
vector <int> add[N];
vector <int> del[N];
void solve() {
cin >> n >> m;
cin >> budget;
cin >> p;
x.resize(p);
y.resize(p);
x2.resize(p);
y2.resize(p);
cost.resize(p);
for (int i = 0; i < p; i++) {
cin >> x[i] >> y[i] >> x2[i] >> y2[i] >> cost[i];
}
for (int i = 0; i < p; i++) {
add[x[i]].push_back(i);
del[x2[i] + 1].push_back(i);
}
SegmentTree tree(m + 1);
for (auto i : add[1]) {
tree.add(y[i], y2[i], 1);
}
int r = 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (auto i : del[i]) {
tree.add(y[i], y2[i], -1);
}
while (r <= n && tree.get() >= r - i + 1) {
ans = max(ans, r - i + 1);
r++;
for (auto i : add[r]) {
tree.add(y[i], y2[i], 1);
}
}
}
cout << ans << "\n";
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
//freopen("./input.txt", "r", stdin);
solve();
}
Compilation message
pyramid_base.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
pyramid_base.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int tm = tl + tr >> 1;
| ~~~^~~~
pyramid_base.cpp: In member function 'void SegmentTree::build(int, int, int)':
pyramid_base.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int tm = tl + tr >> 1;
| ~~~^~~~
pyramid_base.cpp: In member function 'void SegmentTree::combine(int, int, int)':
pyramid_base.cpp:90:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | int tm = tl + tr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
47196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
51800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
76536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
74836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
48220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
52816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
81848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
81636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
82448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
101144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
537 ms |
110528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
683 ms |
118100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
