Submission #1016655

#TimeUsernameProblemLanguageResultExecution timeMemory
1016655serkanrashidWall (IOI14_wall)C++14
0 / 100
109 ms18216 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; struct Node { int ch,ty; Node() { ch = 0; 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; 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 { lazy[v*2+0].ch = min(lazy[v*2+0].ch,lazy[v].ch); 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 = 0; lazy[v].ty = 0; } void query(int v, int l, int r) { push_lazy(v,l,r); if(l==r) return; int mid = (l+r)/2; if(qr<=mid) query(v*2+0,l,mid+0); else 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) { for(int j = 0; j < n; j++) { ql = qr = j; query(1,0,n-1); } f = false; } type = op[i]; ql = left[i]; qr = right[i]; val = height[i]; update(1,0,n-1); } for(int j = 0; j < n; j++) { ql = qr = j; 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...