#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
const int NS = (int)8e5 + 54;
int tr[NS * 4], tr2[NS * 4], l[NS * 4], r[NS * 4];
vector<int> srt;
struct Data{
int xs, ys, ye, v;
Data(){}
Data(int xs, int ys, int ye, int v):xs(xs), ys(ys), ye(ye), v(v){}
bool operator<(const Data&r)const{
return xs < r.xs || (xs == r.xs && v > r.v);
}
};
void build(int x, int s, int e){
if(s == e){
tr[x] = l[x] = r[x] = srt[s + 1] - srt[s];
return;
}
int m = s + e >> 1;
build(x * 2, s, m), build(x * 2 + 1, m + 1, e);
tr[x] = l[x] = r[x] = tr[x * 2] + tr[x * 2 + 1];
}
void push(int x, int s, int e, int ps, int pe, int val){
//cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << endl;
if(pe < s || ps > e) return;
if(ps <= s && pe >= e){
tr2[x] += val;
if(!tr2[x]){
if(s == e) tr[x] = l[x] = r[x] = srt[s + 1] - srt[s];
else{
tr[x] = max({tr[x * 2], tr[x * 2 + 1], r[x * 2] + l[x * 2 + 1]});
l[x] = (tr[x * 2] == srt[(s + e) / 2 + 1] - srt[s] ? tr[x * 2] + l[x * 2 + 1] : l[x * 2]);
r[x] = (tr[x * 2 + 1] == srt[e + 1] - srt[(s + e) / 2 + 1] ? tr[x * 2 + 1] + r[x * 2] : r[x * 2 + 1]);
}
}
else{
tr[x] = l[x] = r[x] = 0;
}
return;
}
int m = s + e >> 1;
push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val);
if(!tr2[x]){
if(s == e) tr[x] = l[x] = r[x] = srt[s + 1] - srt[s];
else{
tr[x] = max({tr[x * 2], tr[x * 2 + 1], r[x * 2] + l[x * 2 + 1]});
l[x] = (tr[x * 2] == srt[(s + e) / 2 + 1] - srt[s] ? tr[x * 2] + l[x * 2 + 1] : l[x * 2]);
r[x] = (tr[x * 2 + 1] == srt[e + 1] - srt[(s + e) / 2 + 1] ? tr[x * 2 + 1] + r[x * 2] : r[x * 2 + 1]);
}
}
else{
tr[x] = l[x] = r[x] = 0;
}
}
struct Seg{
int n;
vector<int> tree, lazy;
Seg(int N):n(N){
tree.resize(n * 4), lazy.resize(n * 4);
}
void add(int x, int l, int r, int val){
lazy[x] += val;
tree[x] += val;
}
void update(int x, int l, int r){
if(lazy[x] == 0) return;
int mid = (l + r) >> 1;
add(x * 2, l, mid, lazy[x]), add(x * 2 + 1, mid + 1, r, lazy[x]);
lazy[x] = 0;
}
void push(int x, int l, int r, int pl, int pr, int val){
if(pr < l || pl > r || pl > pr) return;
if(l >= pl && r <= pr){
add(x, l, r, val);
return;
}
update(x, l, r);
int mid = (l + r) >> 1;
push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
}
int get(int x, int l, int r, int fl, int fr){
if(fr < l || fl > r || fl > fr) return (int)1e9;
if(l >= fl && r <= fr) return tree[x];
update(x, l, r);
int mid = (l + r) >> 1;
return min(get(x * 2, l, mid, fl, fr), get(x * 2 + 1, mid + 1, r, fl, fr));
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int h, w, n, b;
cin >> h >> w >> b >> n;
vector<vector<int>> a(n, vector<int>(5));
for(int i = 0; i < n; ++i){
for(int j = 0; j < 5; ++j){
cin >> a[i][j];
}
}
int ans = 0;
if(b){
int low = 0, high = (int)1e6;
vector<Data> vc;
while(low < high){
int mid = low + high + 1 >> 1;
srt.clear();
for(int i = 0; i < n; ++i){
srt.push_back(a[i][1] - mid + 1), srt.push_back(a[i][3] + 1);
}
srt.push_back(1), srt.push_back(w + 1);
srt.push_back(w - mid + 1);
sort(srt.begin(), srt.end());
srt.erase(unique(srt.begin(), srt.end()), srt.end());
vector<Data> vc;
for(int i = 0; i < n; ++i){
a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1] - mid + 1) - srt.begin();
a[i][3] = lower_bound(srt.begin(), srt.end(), a[i][3] + 1) - srt.begin();
}
for(int i = 0; i < n; ++i){
vc.push_back(Data(a[i][0] - mid + 1, a[i][1], a[i][3] - 1, a[i][4]));
vc.push_back(Data(a[i][2] + 1, a[i][1], a[i][3] - 1, -a[i][4]));
}
sort(vc.begin(), vc.end());
int lst = 1, f = 0;
Seg tree((int)srt.size() + 4);
int up = lower_bound(srt.begin(), srt.end(), w - mid + 1) - srt.begin();
int down = lower_bound(srt.begin(), srt.end(), 1) - srt.begin();
for(auto&i:vc){
if(lst < i.xs && lst >= 1 && lst + mid - 1 <= h){
if(tree.get(1, 0, (int)srt.size() - 2, down, up) <= b){
f = 1;
break;
}
}
lst = i.xs;
tree.push(1, 0, (int)srt.size() - 2, i.ys, i.ye, i.v);
}
if(lst >= 1 && lst + mid - 1 <= h){
if(tree.get(1, 0, (int)srt.size() - 2, down, up) <= b){
f = 1;
}
}
if(f){
low = mid;
}
else{
high = mid - 1;
}
for(int i = 0; i < n; ++i){
a[i][1] = srt[a[i][1]] + mid - 1;
a[i][3] = srt[a[i][3]] - 1;
}
}
ans = low;
}
else{
for(int k = 0; k < 2; ++k){
srt.clear();
for(int i = 0; i < n; ++i){
srt.push_back(a[i][1]), srt.push_back(a[i][3] + 1);
}
srt.push_back(1), srt.push_back(w + 1);
sort(srt.begin(), srt.end());
srt.erase(unique(srt.begin(), srt.end()), srt.end());
vector<Data> vc;
for(int i = 0; i < n; ++i){
a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1]) - srt.begin();
a[i][3] = lower_bound(srt.begin(), srt.end(), a[i][3] + 1) - srt.begin();
vc.push_back(Data(a[i][0], a[i][1], a[i][3] - 1, 1));
vc.push_back(Data(a[i][2] + 1, a[i][1], a[i][3] - 1, -1));
}
vc.push_back(Data(1, 0, (int)srt.size() - 2, 1));
vc.push_back(Data(1, 0, (int)srt.size() - 2, -1));
vc.push_back(Data(h + 1, 0, (int)srt.size() - 2, 1));
vc.push_back(Data(h + 1, 0, (int)srt.size() - 2, -1));
sort(vc.begin(), vc.end());
build(1, 0, (int)srt.size() - 2);
int r = 0, mr = -1;
for(int l = 0; l < (int)vc.size(); ++l){
if(vc[l].v == -1){
push(1, 0, (int)srt.size() - 2, vc[l].ys, vc[l].ye, -1);
}
while(r + 1 < (int)vc.size()){
if(tr[1] < vc[r].xs - vc[l].xs){
break;
}
mr = vc[r].xs;
if(tr[1] >= vc[r].xs - vc[l].xs) mr = vc[r].xs;
if(vc[r].v == 1) push(1, 0, (int)srt.size() - 2, vc[r].ys, vc[r].ye, 1);
++r;
}
if(tr[1] >= vc[r].xs - vc[l].xs){
mr = vc[r].xs;
}
if(r){
ma(ans, mr - vc[l].xs);
//cout << vc[l].xs << ' ' << vc[l].ys << ' ' << vc[l].ye << ' ' << vc[l].v << endl;
//cout << vc[r - 1].xs << ' ' << vc[r - 1].ys << ' ' << vc[r - 1].ye << ' ' << vc[r - 1].v << endl;
}
}
for(int i = 0; i < n; ++i){
a[i][1] = srt[a[i][1]];
a[i][3] = srt[a[i][3]] - 1;
swap(a[i][0], a[i][1]);
swap(a[i][2], a[i][3]);
}
swap(h, w);
}
}
cout << ans << '\n';
return 0;
}
Compilation message
pyramid_base.cpp: In function 'void build(long long int, long long int, long long int)':
pyramid_base.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int m = s + e >> 1;
| ~~^~~
pyramid_base.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int, long long int)':
pyramid_base.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int m = s + e >> 1;
| ~~^~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:115:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int mid = low + high + 1 >> 1;
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
716 KB |
Output is correct |
| 2 |
Correct |
4 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
700 KB |
Output is correct |
| 2 |
Correct |
4 ms |
700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
1708 KB |
Output is correct |
| 2 |
Correct |
130 ms |
1732 KB |
Output is correct |
| 3 |
Correct |
130 ms |
1656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
422 ms |
4884 KB |
Output is correct |
| 2 |
Correct |
487 ms |
5028 KB |
Output is correct |
| 3 |
Correct |
387 ms |
4696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
7388 KB |
Output is correct |
| 2 |
Correct |
259 ms |
5804 KB |
Output is correct |
| 3 |
Correct |
591 ms |
7176 KB |
Output is correct |
| 4 |
Correct |
507 ms |
7220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
698 ms |
8392 KB |
Output is correct |
| 2 |
Correct |
751 ms |
8232 KB |
Output is correct |
| 3 |
Incorrect |
653 ms |
8440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
865 ms |
9624 KB |
Output is correct |
| 2 |
Correct |
1014 ms |
9476 KB |
Output is correct |
| 3 |
Correct |
933 ms |
9428 KB |
Output is correct |
| 4 |
Correct |
988 ms |
9540 KB |
Output is correct |
| 5 |
Correct |
946 ms |
9420 KB |
Output is correct |
| 6 |
Incorrect |
795 ms |
9980 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
890 ms |
80308 KB |
Output is correct |
| 2 |
Correct |
471 ms |
55660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1349 ms |
108576 KB |
Output is correct |
| 2 |
Correct |
1255 ms |
109188 KB |
Output is correct |
| 3 |
Correct |
751 ms |
92332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1633 ms |
147320 KB |
Output is correct |
| 2 |
Correct |
1865 ms |
117552 KB |
Output is correct |
| 3 |
Correct |
1886 ms |
117540 KB |
Output is correct |
| 4 |
Correct |
1645 ms |
117592 KB |
Output is correct |
| 5 |
Correct |
1103 ms |
101196 KB |
Output is correct |
