Submission #1016667

#TimeUsernameProblemLanguageResultExecution timeMemory
1016667serkanrashidWall (IOI14_wall)C++14
0 / 100
106 ms15064 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; struct Node { int ch,ty; Node() { ch = -1; ty = 0; }; Node(int chi, int ti) { ch = chi; ty = ti; } }; const int maxn = 2e5+5; int type,ql,qr,val; Node lazy[4*maxn]; int tree[maxn]; void push_lazy(int v, int l, int r) { if(lazy[v].ty==0) return; ///cout << v << " " << l << " " << r << endl; ///cout << lazy[v].ch << " " << lazy[v].ty << endl; if(l!=r) { if(lazy[v].ty==1) { lazy[v*2+0].ch = max(lazy[v*2+0].ch,lazy[v].ch); lazy[v*2+1].ch = max(lazy[v*2+1].ch,lazy[v].ch); } else { if(lazy[v*2+0].ch==-1) lazy[v*2+0].ch = lazy[v].ch; else lazy[v*2+0].ch = min(lazy[v*2+0].ch,lazy[v].ch); if(lazy[v*2+1].ch==-1) lazy[v*2+1].ch = lazy[v].ch; else lazy[v*2+1].ch = min(lazy[v*2+1].ch,lazy[v].ch); } } else { if(lazy[v].ty==1) tree[r] = max(tree[r],lazy[v].ch); else tree[r] = min(tree[r],lazy[v].ch); } lazy[v].ch = -1; lazy[v].ty = 0; } void query(int v, int l, int r) { ///cout << "query" << endl; push_lazy(v,l,r); if(l==r) return; int mid = (l+r)/2; query(v*2+0,l,mid+0); query(v*2+1,mid+1,r); } void update(int v, int l, int r) { push_lazy(v,l,r); if(r<ql||qr<l||l>r) return; if(ql<=l&&r<=qr) { lazy[v] = {val,type}; push_lazy(v,l,r); /// return; } int mid = (l+r)/2; update(v*2+0,l,mid+0); update(v*2+1,mid+1,r); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { bool f = true; for(int i = 0; i < k; i++) { if(f&&op[i]==2) { query(1,0,n-1); f = false; } type = op[i]; ql = left[i]; qr = right[i]; val = height[i]; update(1,0,n-1); } query(1,0,n-1); for(int i = 0; i < n; i++) finalHeight[i] = tree[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...