#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll M, N, P, B;
const ll S = (1 << 21);
struct LazySegTree{
ll T[2 * S] = {};
ll lazy[2 * S] = {};
void update(ll l, ll r, ll v) {update(1, 1, S, l, r, v);}
ll query(ll l, ll r) {return query(1, 1, S, l, r);}
void propagate(ll node, ll s, ll e){
ll lch = 2 * node, rch = 2 * node + 1;
if(s != e){
lazy[lch] += lazy[node], lazy[rch] += lazy[node];
}
T[node] += lazy[node];
lazy[node] = 0;
}
void update(ll node, ll s, ll e, ll l, ll r, ll v){
propagate(node, s, e);
if(e < l || s > r) return;
if(l <= s && e <= r){
lazy[node] += v;
propagate(node, s, e);
return;
}
ll lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
update(lch, s, m, l, r, v);
update(rch, m + 1, e, l, r, v);
T[node] = min(T[lch], T[rch]);
}
ll query(ll node, ll s, ll e, ll l, ll r){
propagate(node, s, e);
if(e < l || s > r) return 1e15;
if(l <= s && e <= r) return T[node];
ll lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
ll x = query(lch, s, m, l, r), y = query(rch, m + 1, e, l, r);
return min(x, y);
}
};
struct Rect{
ll x1, y1, x2, y2, c;
bool operator<(const Rect &r)const{
return x1 < r.x1;
}
};
Rect A[400005];
struct Node{
int l, r, mn, len, pfx, sfx, d;
Node operator+(const Node &k)const{
Node ret = {l, k.r, min(mn, k.mn), len + k.len, pfx, k.sfx, 0LL};
if(mn == ret.mn) ret.d = max(ret.d, d);
if(k.mn == ret.mn) ret.d = max(ret.d, k.d);
if(pfx == len && l == k.l) ret.pfx = len + k.pfx;
if(k.sfx == k.len && r == k.r) ret.sfx = k.len + sfx;
if(r == k.l && r == ret.mn) ret.d = max(ret.d, sfx + k.pfx);
return ret;
}
};
struct SegTree{
Node T[2 * S];
int lazy[2 * S] = {};
void init(int node, int s, int e){
if(s == e){
T[node] = {0, 0, 0, 1, 1, 1, 1};
return;
}
int lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
init(lch, s, m);
init(rch, m + 1, e);
T[node] = T[lch] + T[rch];
}
void propagate(int node, int s, int e){
int lch = 2 * node, rch = 2 * node + 1;
if(s != e){
lazy[lch] += lazy[node], lazy[rch] += lazy[node];
}
T[node].l += lazy[node];
T[node].r += lazy[node];
T[node].mn += lazy[node];
lazy[node] = 0;
}
void update(int node, int s, int e, int l, int r, int v){
propagate(node, s, e);
if(e < l || s > r) return;
if(l <= s && e <= r){
lazy[node] += v;
propagate(node, s, e);
return;
}
int lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
update(lch, s, m, l, r, v);
update(rch, m + 1, e, l, r, v);
T[node] = T[lch] + T[rch];
}
int query(){
return (T[1].mn == 0 ? T[1].d : 0);
}
};
SegTree ST;
struct Line{
int y1, y2, c;
};
vector<Line> L[1000005], R[1000005];
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> M >> N >> B >> P;
if(B == 0){
for(int i = 1; i <= P; i++){
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
L[x1].push_back({y1, y2, c});
R[x2].push_back({y1, y2, -c});
}
int ans = 0;
int S = 1, E = 1;
ST.init(1, 1, N);
for(auto i : L[1]) ST.update(1, 1, N, i.y1, i.y2, i.c);
while(S <= E && E <= M){
int v = ST.query();
if(v >= E - S + 1){
ans = max(ans, E - S + 1);
E++;
for(auto i : L[E]) ST.update(1, 1, N, i.y1, i.y2, i.c);
} else {
for(auto i : R[S]) ST.update(1, 1, N, i.y1, i.y2, i.c);
S++;
}
}
cout << ans;
} else {
for(int i = 1; i <= P; i++){
cin >> A[i].x1 >> A[i].y1 >> A[i].x2 >> A[i].y2 >> A[i].c;
}
LazySegTree LST;
ll L = 0, R = min(M, N);
while(L <= R){
ll K = (L + R) / 2;
vector<ll> Y;
vector<Rect> T;
ll ans = 1e15;
for(int i = 1; i <= P; i++){
T.push_back({A[i].x1 - K + 1, A[i].y1 - K + 1, A[i].x1 - K + 1, A[i].y2, A[i].c});
T.push_back({A[i].x2 + 1, A[i].y1 - K + 1, A[i].x2 + 1, A[i].y2, -A[i].c});
}
for(int i = 0; i < T.size(); i++){
T[i].y1 = max(T[i].y1, 1LL);
T[i].y2 = min(T[i].y2, N);
}
sort(T.begin(), T.end());
ll last = 0;
for(int i = 1; i <= M - K + 1; i++){
while(last < T.size() && T[last].x1 <= i){
LST.update(T[last].y1, T[last].y2, T[last].c);
last++;
}
ans = min(ans, LST.query(1, N - K + 1));
}
while(last < T.size()){
LST.update(T[last].y1, T[last].y2, T[last].c);
last++;
}
if(ans <= B){
L = K + 1;
} else {
R = K - 1;
}
}
cout << L - 1;
}
}
Compilation message
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:151:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i = 0; i < T.size(); i++){
| ~~^~~~~~~~~~
pyramid_base.cpp:158:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | while(last < T.size() && T[last].x1 <= i){
| ~~~~~^~~~~~~~~~
pyramid_base.cpp:164:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | while(last < T.size()){
| ~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
50 ms |
129352 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
51 ms |
129316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
56 ms |
129384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
52 ms |
130216 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
136592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
101 ms |
186952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
101 ms |
186932 KB |
Output is correct |
| 2 |
Incorrect |
93 ms |
186792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
114 ms |
130592 KB |
Output is correct |
| 2 |
Correct |
150 ms |
130724 KB |
Output is correct |
| 3 |
Correct |
138 ms |
130716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
497 ms |
132432 KB |
Output is correct |
| 2 |
Correct |
598 ms |
133004 KB |
Output is correct |
| 3 |
Correct |
552 ms |
133008 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1655 ms |
134428 KB |
Output is correct |
| 2 |
Correct |
3411 ms |
134876 KB |
Output is correct |
| 3 |
Correct |
355 ms |
134932 KB |
Output is correct |
| 4 |
Correct |
3059 ms |
135092 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2217 ms |
134904 KB |
Output is correct |
| 2 |
Correct |
3214 ms |
135832 KB |
Output is correct |
| 3 |
Correct |
1503 ms |
135760 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1735 ms |
135608 KB |
Output is correct |
| 2 |
Correct |
3538 ms |
136492 KB |
Output is correct |
| 3 |
Correct |
3483 ms |
136464 KB |
Output is correct |
| 4 |
Correct |
3494 ms |
136484 KB |
Output is correct |
| 5 |
Correct |
3492 ms |
136456 KB |
Output is correct |
| 6 |
Correct |
1107 ms |
136828 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
754 ms |
198236 KB |
Output is correct |
| 2 |
Correct |
373 ms |
142792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
958 ms |
203276 KB |
Output is correct |
| 2 |
Incorrect |
386 ms |
200624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1191 ms |
207964 KB |
Output is correct |
| 2 |
Correct |
448 ms |
206296 KB |
Output is correct |
| 3 |
Incorrect |
457 ms |
206332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
