Submission #986361

#TimeUsernameProblemLanguageResultExecution timeMemory
986361PyqeWall (IOI14_wall)C++17
100 / 100
789 ms232496 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; int sq[2000069],inf=1e9; struct segtree { int l,r,lz[2]; segtree *p[2]; void bd(int lh,int rh) { int ii; l=lh; r=rh; lz[0]=-inf; lz[1]=inf; if(l==r) { for(ii=0;ii<2;ii++) { lz[ii]=0; } } else { int md=(l+r)/2; for(ii=0;ii<2;ii++) { p[ii]=new segtree; p[ii]->bd(!ii?l:md+1,!ii?md:r); } } } void ad(int ky,int w) { int ii,u=!ky*2-1; for(ii=0;ii<2;ii++) { lz[ii]=max(lz[ii]*u,w*u)*u; } } void blc() { int ii,iii; for(ii=0;ii<2;ii++) { for(iii=0;iii<2;iii++) { p[ii]->ad(iii,lz[iii]); } } lz[0]=-inf; lz[1]=inf; } void ud(int ky,int lh,int rh,int w) { if(l>rh||r<lh); else if(l>=lh&&r<=rh) { ad(ky,w); } else { int ii; blc(); for(ii=0;ii<2;ii++) { p[ii]->ud(ky,lh,rh,w); } } } void trv() { if(l==r) { sq[l]=lz[0]; } else { int ii; blc(); for(ii=0;ii<2;ii++) { p[ii]->trv(); } } } } sg; void buildWall(int n,int t,int kya[],int la[],int ra[],int wg[],int sqq[]) { int rr,i; sg.bd(0,n-1); for(rr=0;rr<t;rr++) { sg.ud(kya[rr]-1,la[rr],ra[rr],wg[rr]); } sg.trv(); for(i=0;i<n;i++) { sqq[i]=sq[i]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...