Submission #123039

#TimeUsernameProblemLanguageResultExecution timeMemory
123039ansol4328수족관 2 (KOI13_aqua2)C++11
100 / 100
721 ms51300 KiB
#include<stdio.h> #include<vector> #include<queue> #include<utility> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> P; const int INF=1e9; struct SegTree { vector<int> hole, lwall, rwall, wheight, wlazy; vector<double> time, lazy; int base; SegTree(int a) { base=1; while(base<a) base<<=1; hole.resize(base*2+2); lwall.resize(base*2+2); //maximize rwall.resize(base*2+2,INF); //minimize time.resize(base*2+2); lazy.resize(base*2+2); wheight.resize(base*2+2); wlazy.resize(base*2+2); base--; } void update_hole(int idx, int val) { idx+=base; hole[idx]+=val; idx>>=1; while(idx!=0) { hole[idx]=hole[idx*2]+hole[idx*2+1]; idx>>=1; } } int hole_num(int st, int fn, int ns=1, int nf=-1, int num=1) { if(nf==-1) nf=base+1; if(nf<st || fn<ns) return 0; if(st<=ns && nf<=fn) return hole[num]; int mid=(ns+nf)>>1; return hole_num(st,fn,ns,mid,num*2)+hole_num(st,fn,mid+1,nf,num*2+1); } int get_lwall(int st, int fn, int ns=1, int nf=-1, int num=1) { if(nf==-1) nf=base+1; if(nf<st || fn<ns) return 0; if(st<=ns && nf<=fn) return lwall[num]; int mid=(ns+nf)>>1; return max(get_lwall(st,fn,ns,mid,num*2),get_lwall(st,fn,mid+1,nf,num*2+1)); } void update_wall(int idx) { int val=idx; idx+=base; lwall[idx]=val; rwall[idx]=val; idx>>=1; while(idx!=0) { lwall[idx]=max(lwall[idx*2],lwall[idx*2+1]); rwall[idx]=min(rwall[idx*2],rwall[idx*2+1]); idx>>=1; } } int get_rwall(int st, int fn, int ns=1, int nf=-1, int num=1) { if(nf==-1) nf=base+1; if(nf<st || fn<ns) return INF; if(st<=ns && nf<=fn) return rwall[num]; int mid=(ns+nf)>>1; return min(get_rwall(st,fn,ns,mid,num*2),get_rwall(st,fn,mid+1,nf,num*2+1)); } 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]; } time[num]+=lazy[num]; lazy[num]=0; } } void add_time(double 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(nf<st || fn<ns) return; if(st<=ns && nf<=fn) { lazy[num]=val; propagate(ns,nf,num); return; } int mid=(ns+nf)>>1; add_time(val,st,fn,ns,mid,num*2); add_time(val,st,fn,mid+1,nf,num*2+1); time[num]=time[num*2]+time[num*2+1]; } void pro_height(int ns, int nf, int num) { if(wlazy[num]!=0) { if(ns<nf) { wlazy[num*2]=max(wlazy[num*2],wlazy[num]); wlazy[num*2+1]=max(wlazy[num*2+1],wlazy[num]); } wheight[num]=max(wheight[num],wlazy[num]); wlazy[num]=0; } } void change_height(int val, int st, int fn, int ns=1, int nf=-1, int num=1) { if(nf==-1) nf=base+1; pro_height(ns,nf,num); if(nf<st || fn<ns) return; if(st<=ns && nf<=fn) { wlazy[num]=max(wlazy[num],val); pro_height(ns,nf,num); return; } int mid=(ns+nf)>>1; change_height(val,st,fn,ns,mid,num*2); change_height(val,st,fn,mid+1,nf,num*2+1); wheight[num]=max(wheight[num*2],wheight[num*2+1]); } int get_height(int st, int fn, int ns=1, int nf=-1, int num=1) { if(nf==-1) nf=base+1; pro_height(ns,nf,num); if(nf<st || fn<ns) return 0; if(st<=ns && nf<=fn) return wheight[num]; int mid=(ns+nf)>>1; return max(get_height(st,fn,ns,mid,num*2),get_height(st,fn,mid+1,nf,num*2+1)); } }; struct in { int st, fn, height; in() {} in(int a, int b, int c) : st(a), fn(b), height(c) {} }; bool cmp(const in &x, const in &y) { return x.height<y.height || (x.height==y.height && x.st<y.st); } int n; int m[300005][2], h, w; in line[150005]; int hn, hcnt[500005]; int main() { int c=0; ll tot=0; scanf("%d",&n); scanf("%d %d",&m[1][0],&m[1][1]); m[1][0]++; for(int i=2 ; i<n ; i+=2) { scanf("%d %d",&m[i][0],&m[i][1]); scanf("%d %d",&m[i+1][0],&m[i+1][1]); m[i][0]++, m[i+1][0]++; line[++c]=in(m[i][0],m[i+1][0],m[i][1]); tot+=(ll)(m[i+1][0]-m[i][0])*(ll)m[i][1]; } scanf("%d %d",&m[n][0],&m[n][1]); m[n][0]++; w=m[n][0]; scanf("%d",&hn); for(int i=1 ; i<=hn ; i++) { int x1, y1, x2 ,y2; scanf("%d %d",&x1,&y1); scanf("%d %d",&x2,&y2); x1++, x2++; hcnt[x1]++; } SegTree T(w); for(int i=1 ; i<=w ; i++) { if(hcnt[i]!=0) T.update_hole(i,hcnt[i]); } sort(line+1,line+1+c,cmp); T.update_wall(1); T.update_wall(w); int idx=1; while(idx<=c) { ll leak=0; ll cur_height=line[idx].height; queue<P> Q; int l=-1, r=-1; do { int st=line[idx].st, fn=line[idx].fn; int lw=T.get_lwall(1,st); int rw=T.get_rwall(fn,w); ll wh=T.get_height(lw,rw-1); Q.push(P(st,fn)); if(l!=lw) { l=lw, r=rw; int hole_num=T.hole_num(l,r-1); if(hole_num>0) { ll block=(ll)(r-l)*(cur_height-wh); leak+=block; double val=(double)block/hole_num; T.add_time(val,l,r-1); T.change_height((int)cur_height,l,r-1); } } idx++; }while(line[idx].height==line[idx-1].height); tot-=leak; while(!Q.empty()) { P wval=Q.front(); Q.pop(); T.update_wall(wval.first); T.update_wall(wval.second); } } int base=T.base, num=0; for(int len=base+1 ; len>=1 ; len>>=1) { for(int st=1 ; st<=base-len+2 ; st+=len) { int fn=st+len-1; num++; T.propagate(st,fn,num); } } double rest=0; for(int i=1 ; i<=w ; i++) if(hcnt[i]!=0) rest=max(rest,T.time[i+base]); printf("%.2lf\n",rest); printf("%lld",tot); return 0; }

Compilation message (stderr)

aqua2.cpp: In function 'int main()':
aqua2.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua2.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m[1][0],&m[1][1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:175:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&m[i][0],&m[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&m[i+1][0],&m[i+1][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m[n][0],&m[n][1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&hn);
     ~~~~~^~~~~~~~~~
aqua2.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x1,&y1);
         ~~~~~^~~~~~~~~~~~~~~~~
aqua2.cpp:189:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x2,&y2);
         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...