Submission #939737

#TimeUsernameProblemLanguageResultExecution timeMemory
939737asdasdqwerWall (IOI14_wall)C++14
100 / 100
718 ms69512 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; int le; vector<int> lzMin, lzMax; const int minConst = 1e9; const int maxConst = 0; void init (int sz) { le=1; while(le<sz)le*=2; lzMin.assign(2*le, minConst); lzMax.assign(2*le, maxConst); } void pushdown(int x) { if (lzMin[x] == minConst && lzMax[x] == maxConst) { return; } lzMin[2*x+1] = min(max(lzMax[x], lzMin[2*x+1]), lzMin[x]); lzMin[2*x+2] = min(max(lzMax[x], lzMin[2*x+2]), lzMin[x]); lzMax[2*x+1] = max(min(lzMin[x], lzMax[2*x+1]), lzMax[x]); lzMax[2*x+2] = max(min(lzMin[x], lzMax[2*x+2]), lzMax[x]); lzMin[x] = minConst; lzMax[x] = maxConst; } void setVal(int l, int r, int v, int x, int lx, int rx, bool isMax=false) { if (lx >= r || rx <= l) return; if (rx - lx == 1) { if (isMax) { if (lzMax[x] < v) { lzMax[x] = v; } if (lzMin[x] < v) { lzMin[x] = v; } } else { if (lzMin[x] > v) { lzMin[x] = v; } if (lzMax[x] > v) { lzMax[x] = v; } } return; } pushdown(x); if (lx >= l && rx <= r) { if (isMax) { if (lzMax[x] < v) { lzMax[x] = v; } if (lzMin[x] < v) { lzMin[x] = v; } } else { if (lzMin[x] > v) { lzMin[x] = v; } if (lzMax[x] > v) { lzMax[x] = v; } } return; } int m=(lx+rx)/2; setVal(l, r, v, 2*x+1, lx, m, isMax); setVal(l, r, v, 2*x+2, m, rx, isMax); } void setMax(int l, int r, int v) { setVal(l, r, v, 0, 0, le, true); } void setMin(int l, int r, int v) { setVal(l, r, v, 0, 0, le, false); } int get(int i, int x, int lx, int rx) { if (rx-lx==1) { return lzMax[x]; } pushdown(x); int m=(lx+rx)/2; if (i<m)return get(i,2*x+1,lx,m); else return get(i,2*x+2,m,rx); } int get(int i) { return get(i,0,0,le); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { init(n); for (int i=0;i<k;i++) { if (op[i] == 1) { setMax(left[i], right[i]+1, height[i]); } else { setMin(left[i], right[i]+1, height[i]); } } for (int i=0;i<n;i++) { finalHeight[i] = get(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...