Submission #415351

#TimeUsernameProblemLanguageResultExecution timeMemory
415351xyzyzlWall (IOI14_wall)C++14
0 / 100
9 ms864 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e6+5; const int INF = 1e9+7; int n, arr[MAXN], st[4*MAXN], lz1[4*MAXN], lz2[4*MAXN]; void upd(int node, int a, int b, int mn, int mx, int l, int r) { if(l == a && r == b) { st[node] = max(st[node], mx); st[node] = min(st[node], mn); if(mx > lz1[node]) { lz1[node] = lz2[node] = mx; } else if(mn < lz2[node]) { lz1[node] = lz2[node] = mn; } else { lz1[node] = min(lz1[node], mn); lz2[node] = max(lz2[node], mx); } } int mid = (l+r)/2; upd(2*node, l, mid, lz1[node], lz2[node], l, mid); upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r); lz1[node] = INF; lz2[node] = 0; if(b <= mid) { upd(a, b, mn, mx, 2*node, l, mid); } else if(a > mid) { upd(a, b, mn, mx, 2*node+1, mid+1, r); } else { upd(a, mid, mn, mx, 2*node, l, mid); upd(mid+1, b, mn, mx, 2*node+1, mid+1, r); } st[node] = min(st[2*node], st[2*node+1]); } void build(int node, int l, int r) { if(l == r) { lz1[node] = INF; return; } int mid = (l+r)/2; build(node*2, l, mid); build(node*2+1, mid+1, r); lz1[node] = INF; } void convert(int node, int l, int r) { if(l == r) { arr[l] = st[node]; } int mid = (l+r)/2; upd(2*node, l, mid, lz1[node], lz2[node], l, mid); upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r); lz1[node] = INF; lz2[node] = 0; convert(2*node, l, mid); convert(2*node+1, mid+1, r); } void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { n = _n; build(1, 0, n-1); // perform updates for each query. for(int i = 0; i < k; i++) { if(op[i] == 1) { upd(1, left[i], right[i], INF, height[i], 0, n-1); } else { upd(1, left[i], right[i], height[i], 0, 0, n-1); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...