제출 #1183545

#제출 시각아이디문제언어결과실행 시간메모리
1183545sleepntsheepPyramid Base (IOI08_pyramid_base)C++20
0 / 100
2466 ms78300 KiB
#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]; 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); ++n,++m; 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) ,++a[i].x2,++a[i].y2 ; 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+1){ found|=s2.query(0,1,n,mid+1,n)<=b; } } if(found)lower=mid+1; else upper=mid; } printf("%d\n",lower); return 0; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d%d%d", &m, &n, &b, &p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].cost)
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...