Submission #232844

#TimeUsernameProblemLanguageResultExecution timeMemory
232844kshitij_sodaniWall (IOI14_wall)C++17
100 / 100
972 ms138616 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef int64_t llo; #define mp make_pair #define pb puodsh_back #define a first #define b second #include "wall.h" int tree[8000000]; int lazy[8000000][2]; int ans[2000000]; int k; void update(int no,int l,int r,int aa,int bb,int val,int tt){ if(tree[no]<lazy[no][0]){ tree[no]=lazy[no][0]; } else if(tree[no]>lazy[no][1]){ tree[no]=lazy[no][1]; } if(l<r){ if(lazy[no][0]>lazy[no*2+1][1]){ lazy[no*2+1][0]=lazy[no][0]; lazy[no*2+1][1]=lazy[no][0]; } else if(lazy[no][1]<lazy[no*2+1][0]){ lazy[no*2+1][0]=lazy[no][1]; lazy[no*2+1][1]=lazy[no][1]; } else{ lazy[no*2+1][0]=max(lazy[no][0],lazy[no*2+1][0]); lazy[no*2+1][1]=min(lazy[no][1],lazy[no*2+1][1]); } if(lazy[no][0]>lazy[no*2+2][1]){ lazy[no*2+2][0]=lazy[no][0]; lazy[no*2+2][1]=lazy[no][0]; } else if(lazy[no][1]<lazy[no*2+2][0]){ lazy[no*2+2][0]=lazy[no][1]; lazy[no*2+2][1]=lazy[no][1]; } else{ lazy[no*2+2][0]=max(lazy[no][0],lazy[no*2+2][0]); lazy[no*2+2][1]=min(lazy[no][1],lazy[no*2+2][1]); } } lazy[no][0]=0; lazy[no][1]=100001; if(r<aa or l>bb or l>r){ return ; } if(aa<=l and r<=bb){ if(tt==0){ tree[no]=min(tree[no],val); } else{ tree[no]=max(tree[no],val); } // cout<<l<<","<<r<<","<<val<<","<<tree[no]<<"<"<<no<<endl; if(l<r){ if(tt==0){ lazy[no*2+1][0]=min(lazy[no*2+1][0],val); lazy[no*2+1][1]=min(lazy[no*2+1][1],val); } else{ lazy[no*2+1][0]=max(lazy[no*2+1][0],val); lazy[no*2+1][1]=max(lazy[no*2+1][1],val); } if(tt==0){ lazy[no*2+2][0]=min(lazy[no*2+2][0],val); lazy[no*2+2][1]=min(lazy[no*2+2][1],val); } else{ lazy[no*2+2][0]=max(lazy[no*2+2][0],val); lazy[no*2+2][1]=max(lazy[no*2+2][1],val); } } } else{ int mid=(l+r)/2; update(no*2+1,l,mid,aa,bb,val,tt); update(no*2+2,mid+1,r,aa,bb,val,tt); } } int fin(int no,int l,int r){ if(tree[no]<lazy[no][0]){ tree[no]=lazy[no][0]; } else if(tree[no]>lazy[no][1]){ tree[no]=lazy[no][1]; } if(l<r){ if(lazy[no][0]>lazy[no*2+1][1]){ lazy[no*2+1][0]=lazy[no][0]; lazy[no*2+1][1]=lazy[no][0]; } else if(lazy[no][1]<lazy[no*2+1][0]){ lazy[no*2+1][0]=lazy[no][1]; lazy[no*2+1][1]=lazy[no][1]; } else{ lazy[no*2+1][0]=max(lazy[no][0],lazy[no*2+1][0]); lazy[no*2+1][1]=min(lazy[no][1],lazy[no*2+1][1]); } if(lazy[no][0]>lazy[no*2+2][1]){ lazy[no*2+2][0]=lazy[no][0]; lazy[no*2+2][1]=lazy[no][0]; } else if(lazy[no][1]<lazy[no*2+2][0]){ lazy[no*2+2][0]=lazy[no][1]; lazy[no*2+2][1]=lazy[no][1]; } else{ lazy[no*2+2][0]=max(lazy[no][0],lazy[no*2+2][0]); lazy[no*2+2][1]=min(lazy[no][1],lazy[no*2+2][1]); } } lazy[no][0]=0; lazy[no][1]=100001; if(l==r){ ans[l]=tree[no]; } if(l<r){ int mid=(l+r)/2; fin(no*2+1,l,mid); fin(no*2+2,mid+1,r); } } void buildWall(int n, int kk, int op[], int left[], int right[],int height[], int finalHeight[]){ for(int i=0;i<8000000;i++){ lazy[i][0]=0; lazy[i][1]=100001; tree[i]=0; } k=kk; for(int i=0;i<kk;i++){ if(op[i]==1){ update(0,0,n-1,left[i],right[i],height[i],1); } else{ update(0,0,n-1,left[i],right[i],height[i],0); } } // cout<<tree[16]<<endl; fin(0,0,n-1); for(int i=0;i<n;i++){ finalHeight[i]=ans[i]; // cout<<ans[i]<<" "; } // return finalHeight; // cout<<endl; } /*int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int op[6]; int left[6];int right[6];int height[6]; op[0]=1; left[0]=1; right[0]=8; height[0]=4; op[1]=2; left[1]=4; right[1]=9; height[1]=1; op[2]=2; left[2]=3; right[2]=6; height[2]=5; op[3]=1; left[3]=0; right[3]=5; height[3]=3; op[4]=1; left[4]=2; right[4]=2; height[4]=5; op[5]=2; left[5]=6; right[5]=7; height[5]=0; int ar[10]; buildWall(10,6,op,left,right,height,ar); for(int i=0;i<10;i++){ cout<<ar[i]<<" "; } cout<<endl; return 0; }*/

Compilation message (stderr)

wall.cpp: In function 'int fin(int, int, int)':
wall.cpp:132:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...