#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int mxP = 4e5;
int m,n,b,p,x1[mxP],y1[mxP],x2[mxP],y2[mxP],c[mxP];
vector<pii> lft, rht;
struct range_add {
int st[1<<21], lz[1<<21];
void push(int t) {
st[t*2] += lz[t];
st[t*2+1] += lz[t];
lz[t*2] += lz[t];
lz[t*2+1] += lz[t];
lz[t] = 0;
}
void upd(int ul, int ur, int v, int t, int l, int r) {
if (ur <= l || r <= ul) return;
if (ul <= l && r <= ur) {
st[t] += v;
lz[t] += v;
return;
}
int m = l+r>>1;
push(t);
upd(ul, ur, v, t*2, l, m);
upd(ul, ur, v, t*2+1, m, r);
st[t] = min(st[t*2], st[t*2+1]);
}
};
bool can_do(int sz) {
range_add st{};
int l = 0;
for (auto [x, s]: rht) {
while (lft[l].first - x <= sz) {
if (l == lft.size()-1) return 0;
st.upd(y1[lft[l].second]-sz+1, y2[lft[l].second]+1, c[lft[l].second], 1, 1, n-sz+2);
l++;
}
if (~s) st.upd(y1[s]-sz+1, y2[s]+1, -c[s], 1, 1, n-sz+2);
if (st.st[1] <= b) return 1;
}
return 0;
}
struct max_zeros {
int st[1<<21], ans[1<<21], pfx[1<<21], sfx[1<<21];
void build(int t, int l, int r) {
if (r - l > 1) {
int m = l+r>>1;
build(t*2, l, m);
build(t*2+1, m, r);
}
ans[t] = pfx[t] = sfx[t] = r-l;
}
void pull(int t, int l, int r) {
int m = l+r>>1;
pfx[t] = pfx[t*2] + (pfx[t*2] == m-l ? pfx[t*2+1] : 0);
sfx[t] = sfx[t*2+1] + (sfx[t*2+1] == r-m ? sfx[t*2] : 0);
ans[t] = max({ans[t*2], ans[t*2+1], sfx[t*2] + pfx[t*2+1]});
}
void upd(int ul, int ur, int v, int t, int l, int r) {
if (ur <= l || r <= ul) return;
if (ul <= l && r <= ur) {
st[t] += v;
if (!st[t]) {
if (r-l>1) pull(t, l, r);
else ans[t] = pfx[t] = sfx[t] = 1;
}
else ans[t] = pfx[t] = sfx[t] = 0;
return;
}
int m = l+r>>1;
upd(ul, ur, v, t*2, l, m);
upd(ul, ur, v, t*2+1, m, r);
if (!st[t]) pull(t, l, r);
}
};
void sub3() {
int ans = 0, l= 0;
max_zeros st{};
st.build(1, 1, n+1);
for (auto [x, s]: rht) {
while (lft[l].first <= x) {
st.upd(y1[lft[l].second], y2[lft[l].second]+1, 1, 1, 1, n+1);
l++;
}
if (~s) st.upd(y1[s], y2[s]+1, -1, 1, 1, n+1);
while (l < lft.size() && st.ans[1] >= lft[l].first-x-1) {
ans = max(ans, lft[l].first-x-1);
st.upd(y1[lft[l].second], y2[lft[l].second]+1, 1, 1, 1, n+1);
l++;
}
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n >> b >> p;
lft.push_back({m+1, -1});
rht.push_back({0, -1});
for (int i = 0; i < p; ++i) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> c[i];
lft.push_back({x1[i], i});
rht.push_back({x2[i], i});
}
sort(lft.begin(), lft.end());
sort(rht.begin(), rht.end());
if (b == 0) {
sub3();
return 0;
}
int lo = 1, hi = min(m,n)+1, mid;
while (lo != hi) {
mid = lo+hi>>1;
if (can_do(mid)) lo = mid+1;
else hi = mid;
}
cout << lo-1;
}
Compilation message
pyramid_base.cpp: In member function 'void range_add::upd(int, int, int, int, int, int)':
pyramid_base.cpp:27:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int m = l+r>>1;
| ~^~
pyramid_base.cpp: In function 'bool can_do(int)':
pyramid_base.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for (auto [x, s]: rht) {
| ^
pyramid_base.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (l == lft.size()-1) return 0;
| ~~^~~~~~~~~~~~~~~
pyramid_base.cpp: In member function 'void max_zeros::build(int, int, int)':
pyramid_base.cpp:54:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int m = l+r>>1;
| ~^~
pyramid_base.cpp: In member function 'void max_zeros::pull(int, int, int)':
pyramid_base.cpp:61:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int m = l+r>>1;
| ~^~
pyramid_base.cpp: In member function 'void max_zeros::upd(int, int, int, int, int, int)':
pyramid_base.cpp:77:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m = l+r>>1;
| ~^~
pyramid_base.cpp: In function 'void sub3()':
pyramid_base.cpp:88:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for (auto [x, s]: rht) {
| ^
pyramid_base.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | while (l < lft.size() && st.ans[1] >= lft[l].first-x-1) {
| ~~^~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:122:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
122 | mid = lo+hi>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
33124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
67088 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
67112 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
67048 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
17008 KB |
Output is correct |
| 2 |
Correct |
76 ms |
16972 KB |
Output is correct |
| 3 |
Correct |
78 ms |
17024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
17340 KB |
Output is correct |
| 2 |
Correct |
301 ms |
17356 KB |
Output is correct |
| 3 |
Correct |
252 ms |
17380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
17736 KB |
Output is correct |
| 2 |
Correct |
40 ms |
17608 KB |
Output is correct |
| 3 |
Correct |
151 ms |
17576 KB |
Output is correct |
| 4 |
Correct |
359 ms |
17696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
326 ms |
17864 KB |
Output is correct |
| 2 |
Correct |
813 ms |
17852 KB |
Output is correct |
| 3 |
Correct |
118 ms |
17956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
246 ms |
18024 KB |
Output is correct |
| 2 |
Correct |
985 ms |
18032 KB |
Output is correct |
| 3 |
Correct |
934 ms |
18032 KB |
Output is correct |
| 4 |
Correct |
984 ms |
18024 KB |
Output is correct |
| 5 |
Correct |
974 ms |
18020 KB |
Output is correct |
| 6 |
Correct |
90 ms |
17916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
734 ms |
81772 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1025 ms |
88884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1176 ms |
95964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
