#include <stdio.h>
#include <utility>
#include <algorithm>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#define PP 400000
int m, n, b, p;
struct pyramid {
int y1, x1, y2, x2, cost;
} a[PP + 1];
struct {
long long t[4444444], lz[4444444];
void pus(int v,int l,int r){
if(lz[v]){
t[v]+=lz[v];
if(l-r){
lz[v*2+1]+=lz[v];
lz[v*2+2]+=lz[v];
}
lz[v]=0;
}
}
void update(int v,int l,int r,int x,int y,int k){
pus(v,l,r);
if(r<x||y<l)return;
if(x<=l&&r<=y){ lz[v]=k; pus(v,l,r);return; }
update(v*2+1,l,(l+r)/2,x,y,k);update(v*2+2,(l+r)/2+1,r,x,y,k);
t[v]=std::min(t[v*2+1],t[v*2+2]);
}
long long query(int v,int l,int r,int x,int y){
pus(v,l,r);
if(x<=l&&r<=y)return t[v];
if(y<=(l+r)/2)return query(v*2+1,l,(l+r)/2,x,y);
if(x>(l+r)/2)return query(v*2+2,(l+r)/2+1,r,x,y);
return std::min(query(v*2+2,(l+r)/2+1,r,x,y),query(v*2+1,l,(l+r)/2,x,y));
}
void cl(){
memset(t,0,sizeof t);
memset(lz,0,sizeof lz);
}
} s2;
int main() {
srand(time(0));
scanf("%d%d%d%d", &m, &n, &b, &p);
for(int i=0;i<p;++i)
scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].cost);
if(1||b){
static std::pair<int,int>ev[63333];
int lower=0,upper=std::min(n,m)+1;
while(upper-lower>1){
int mid=lower+(upper-lower)/2;
for(int i=0;i<p;++i){
ev[i*2]=std::make_pair(a[i].x1,i);
ev[i*2+1]=std::make_pair(a[i].x2+mid,i|(1<<25));
}
std::sort(ev,ev+2*p);
int i_{},found{};
s2.cl();
for(int i=1;!found&&i<=m;++i){
while(i_<2*p&&ev[i_].first==i){
int i1{ev[i_].second};
if(i1>(1<<20)){
i1^=(1<<25);
s2.update(0,1,n,a[i1].y1,std::max(n,a[i1].y2+mid-1),-a[i1].cost);
}else{
s2.update(0,1,n,a[i1].y1,std::max(n,a[i1].y2+mid-1),a[i1].cost);
}
++i_;
}
if(i>=mid){
found|=s2.query(0,1,n,mid,n)<=b;
}
}
if(found)lower=mid;
else upper=mid;
}
printf("%d\n",lower);
return 0;
}
return 0;
}
Compilation message (stderr)
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d%d%d", &m, &n, &b, &p);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].cost);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |