#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll INF=1e18;
struct SegTree{
vector<ll> tree, lazy;
int base;
SegTree(int a){
base=1;
while(base<a) base<<=1;
tree.resize(base*2+2);
lazy.resize(base*2+2);
base--;
}
void setup(int a){
base=1;
while(base<a) base<<=1;
for(int i=1 ; i<base*2 ; i++) tree[i]=lazy[i]=0;
for(int i=base+a ; i<base*2 ; i++) tree[i]=INF;
for(int i=base-1 ; i>=1 ; i--) tree[i]=min(tree[i*2],tree[i*2+1]);
base--;
}
void propagate(int ns, int nf, int num){
if(lazy[num]!=0){
if(ns<nf){
lazy[num*2]+=lazy[num];
lazy[num*2+1]+=lazy[num];
}
tree[num]+=lazy[num];
lazy[num]=0;
}
}
ll query(int ns=1, int nf=-1, int num=1){
if(nf==-1) nf=base+1;
propagate(ns,nf,num);
return tree[num];
}
void add_value(ll val, int st, int fn, int ns=1, int nf=-1, int num=1){
if(nf==-1) nf=base+1;
propagate(ns,nf,num);
if(ns>fn || nf<st) return;
if(st<=ns && nf<=fn){
lazy[num]+=val;
propagate(ns,nf,num);
return;
}
int mid=(ns+nf)>>1;
add_value(val,st,fn,ns,mid,num*2);
add_value(val,st,fn,mid+1,nf,num*2+1);
tree[num]=min(tree[num*2],tree[num*2+1]);
}
};
struct A{
int x1, y1, x2, y2, c;
A(){}
A(int t1, int t2, int t3, int t4, int t5) : x1(t1), y1(t2), x2(t3), y2(t4), c(t5) {}
};
bool cmp(const A &lhs, const A &rhs){
return lhs.y1==rhs.y1 ? lhs.y2<rhs.y2 : lhs.y1<rhs.y1;
}
int m, n, p;
ll b;
A ob[400005];
vector<int> in[1000005], out[1000005];
SegTree T(1000005);
bool pos(int w)
{
T.setup(m-w+1);
int idx=1, st, fn, k;
for(int i=1 ; i<w ; i++){
for(int k : in[i]){
st=max(1,ob[k].x1-w+1);
fn=min(m-w+1,ob[k].x2);
T.add_value(ob[k].c,st,fn);
}
}
for(int sy=1, fy=w ; fy<=n ; sy++, fy++){
for(int k : in[fy]){
st=max(1,ob[k].x1-w+1);
fn=min(m-w+1,ob[k].x2);
T.add_value(ob[k].c,st,fn);
}
for(int k : out[sy]){
st=max(1,ob[k].x1-w+1);
fn=min(m-w+1,ob[k].x2);
T.add_value(-ob[k].c,st,fn);
}
if(T.query()<=b) return true;
}
return false;
}
int main()
{
scanf("%d %d",&m,&n);
scanf("%lld",&b);
scanf("%d",&p);
for(int i=1 ; i<=p ; i++){
scanf("%d %d %d %d %d",&ob[i].x1,&ob[i].y1,&ob[i].x2,&ob[i].y2,&ob[i].c);
in[ob[i].y1].push_back(i);
out[ob[i].y2+1].push_back(i);
}
int st=1, fn=min(m,n), mid, ans=0;
while(st<=fn){
mid=(st+fn)>>1;
if(pos(mid)) st=mid+1, ans=mid;
else fn=mid-1;
}
printf("%d",ans);
return 0;
}
Compilation message
pyramid_base.cpp: In function 'bool pos(int)':
pyramid_base.cpp:77:9: warning: unused variable 'idx' [-Wunused-variable]
77 | int idx=1, st, fn, k;
| ^~~
pyramid_base.cpp:77:24: warning: unused variable 'k' [-Wunused-variable]
77 | int idx=1, st, fn, k;
| ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%d %d",&m,&n);
| ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
104 | scanf("%lld",&b);
| ~~~~~^~~~~~~~~~~
pyramid_base.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
105 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
pyramid_base.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d %d %d %d %d",&ob[i].x1,&ob[i].y1,&ob[i].x2,&ob[i].y2,&ob[i].c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
80120 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
80120 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
51 ms |
80172 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
64 ms |
80248 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
89 ms |
80248 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
184 ms |
80288 KB |
Output is correct |
| 2 |
Correct |
307 ms |
80256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
323 ms |
80248 KB |
Output is correct |
| 2 |
Correct |
197 ms |
80248 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
71 ms |
80504 KB |
Output is correct |
| 2 |
Correct |
105 ms |
80504 KB |
Output is correct |
| 3 |
Correct |
120 ms |
80504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
301 ms |
81440 KB |
Output is correct |
| 2 |
Correct |
616 ms |
81400 KB |
Output is correct |
| 3 |
Correct |
520 ms |
81272 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
613 ms |
81784 KB |
Output is correct |
| 2 |
Correct |
377 ms |
80964 KB |
Output is correct |
| 3 |
Correct |
90 ms |
81784 KB |
Output is correct |
| 4 |
Correct |
1486 ms |
81820 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1063 ms |
82168 KB |
Output is correct |
| 2 |
Correct |
1774 ms |
81968 KB |
Output is correct |
| 3 |
Correct |
551 ms |
82296 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
851 ms |
82680 KB |
Output is correct |
| 2 |
Correct |
2413 ms |
82552 KB |
Output is correct |
| 3 |
Correct |
2156 ms |
82468 KB |
Output is correct |
| 4 |
Correct |
2338 ms |
82552 KB |
Output is correct |
| 5 |
Correct |
2131 ms |
82552 KB |
Output is correct |
| 6 |
Correct |
429 ms |
82552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5067 ms |
95480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5096 ms |
102264 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5056 ms |
108704 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
