Submission #1016599

#TimeUsernameProblemLanguageResultExecution timeMemory
1016599simona1230Wall (IOI14_wall)C++17
0 / 100
514 ms14260 KiB
#include "wall.h" #include "bits/stdc++.h" using namespace std; struct node { int l,r; int vl,tp; node() {} node(int lf,int rt,int _v,int _t) { l=lf; r=rt; vl=_v; tp=_t; } }; int a[2000001]; struct tree { vector<node> t= {{-1,-1,0,0}}; tree() {} void children(int i) { t.push_back({-1,-1,0,0}); t[i].l=t.size()-1; t.push_back({-1,-1,0,0}); t[i].r=t.size()-1; } void push_lazy(int i,int l,int r) { if(t[i].tp==0)return; if(l!=r) { if(t[i].l==-1)children(i); int i1=t[i].l; int i2=t[i].r; if(t[i1].vl==-1||t[i1].vl<t[i].vl&&t[i].tp==1) { t[i1].vl=t[i].vl; t[i1].tp=t[i].tp; } if(t[i2].vl==-1||t[i2].vl<t[i].vl&&t[i].tp==1) { t[i2].vl=t[i].vl; t[i2].tp=t[i].tp; } if(t[i1].vl==-1||t[i1].vl>t[i].vl&&t[i].tp==2) { t[i1].vl=t[i].vl; t[i1].tp=t[i].tp; } if(t[i2].vl==-1||t[i2].vl>t[i].vl&&t[i].tp==2) { t[i2].vl=t[i].vl; t[i2].tp=t[i].tp; } if(t[i1].vl!=t[i2].vl||t[i1].tp!=t[i2].tp) t[i].vl=-1; else t[i].vl=t[i1].vl,t[i].tp=t[i1].tp; } t[i].tp=0; } void update(int i,int l,int r,int ql,int qr,int val,int type) { //cout<<val<<" "<<type<<endl; push_lazy(i,l,r); if(ql>qr)return; if(ql<=l&&r<=qr) { if(t[i].vl==-1||t[i].vl<val&&type==1) { //cout<<"in"<<endl; t[i].vl=val; t[i].tp=type; } if(t[i].vl==-1||t[i].vl>val&&type==2) { t[i].vl=val; t[i].tp=type; } //cout<<l<<" "<<r<<" "<<t[i].vl<<" "<<t[i].tp<<endl; return; } int m=(l+r)/2; if(t[i].l==-1)children(i); update(t[i].l,l,m,ql,min(qr,m),val,type); update(t[i].r,m+1,r,max(m+1,ql),qr,val,type); int i1=t[i].l,i2=t[i].r; if(t[i1].vl!=t[i2].vl||t[i1].tp!=t[i2].tp) t[i].vl=-1; else t[i].vl=t[i1].vl,t[i].tp=t[i1].tp; //cout<<l<<" - "<<r<<" "<<t[i].vl<<" "<<t[i].tp<<endl; } void fix(int i,int l,int r) { if(t[i].l==-1) { for(int j=l; j<=r; j++) a[j]=t[i].vl; return; } push_lazy(i,l,r); int m=(l+r)/2; fix(t[i].l,l,m); fix(t[i].r,m+1,r); } }; tree t; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { for(int i=0; i<k; i++) { //cout<<height[i]<<" "<<op[i]<<endl; t.update(0,0,n-1,left[i],right[i],height[i],op[i]); } t.fix(0,0,n-1); for(int i=0; i<n; i++) finalHeight[i]=a[i]; }

Compilation message (stderr)

wall.cpp: In member function 'void tree::push_lazy(int, int, int)':
wall.cpp:42:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |             if(t[i1].vl==-1||t[i1].vl<t[i].vl&&t[i].tp==1)
wall.cpp:48:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |             if(t[i2].vl==-1||t[i2].vl<t[i].vl&&t[i].tp==1)
wall.cpp:54:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |             if(t[i1].vl==-1||t[i1].vl>t[i].vl&&t[i].tp==2)
wall.cpp:60:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             if(t[i2].vl==-1||t[i2].vl>t[i].vl&&t[i].tp==2)
wall.cpp: In member function 'void tree::update(int, int, int, int, int, int, int)':
wall.cpp:79:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |             if(t[i].vl==-1||t[i].vl<val&&type==1)
wall.cpp:85:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |             if(t[i].vl==-1||t[i].vl>val&&type==2)
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...