Submission #744646

#TimeUsernameProblemLanguageResultExecution timeMemory
744646angelsWall (IOI14_wall)C++14
100 / 100
613 ms69520 KiB
/****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ #include <bits/stdc++.h> using namespace std; int RIGHT=2097152; int d[5000000], g[5000000]; int N, K; void update(int l, int r, int p, int h, int n, int a, int b) { if(b<l || r<a) return; if(l<=a && b<=r) { if(p==1) //add { d[n]=max(d[n], h); g[n]=max(g[n], h); } if(p==2) //remove { d[n]=min(d[n], h); g[n]=min(g[n], h); } return; } d[2*n]=max(min(d[2*n], d[n]), g[n]); g[2*n]=min(max(g[2*n], g[n]), d[n]); d[2*n+1]=max(min(d[2*n+1], d[n]), g[n]); g[2*n+1]=min(max(g[2*n+1], g[n]), d[n]); d[n]=10000000; g[n]=0; int mid=(a+b)/2; update(l, r, p, h, 2*n, a, mid); update(l, r, p, h, 2*n+1, mid+1, b); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { N=n, K=k; for(int i=0; i<K; i++) { int p, l, r, h; cin>>p>>l>>r>>h; p=op[i]; l=left[i]; r=right[i]; h=height[i]; update(l+1, r+1, p, h, 1, 1, RIGHT); } for(int i=1; i<=RIGHT-1; i++) { d[2*i]=max(min(d[2*i], d[i]), g[i]); g[2*i]=min(max(g[2*i], g[i]), d[i]); d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]); g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]); } for(int i=RIGHT; i<=RIGHT+N-1; i++) { finalHeight[i-RIGHT]=min(d[i],g[i]); } } /*int main() { cin>>N>>K; for(int i=1; i<=K; i++) { int p, l, r, h; cin>>p>>l>>r>>h; update(l+1, r+1, p, h, 1, 1, RIGHT); } for(int i=1; i<=RIGHT-1; i++) { d[2*i]=max(min(d[2*i], d[i]), g[i]); g[2*i]=min(max(g[2*i], g[i]), d[i]); d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]); g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]); } for(int i=RIGHT; i<=RIGHT+N-1; i++) cout<<min(d[i],g[i])<<"\n"; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...