Submission #1041898

#TimeUsernameProblemLanguageResultExecution timeMemory
1041898BF001Wall (IOI14_wall)C++17
100 / 100
434 ms170072 KiB
#include<bits/stdc++.h> using namespace std; #define N 2000005 #define oo (1e9 + 1) int n, k, res[N], q; struct node{ int ma, mi, lma, lmi; node(){ ma = mi = 0; lma = -oo; lmi = oo; } }; vector<node> bit; void add(int id, int ma){ bit[id].mi = max(bit[id].mi, ma); bit[id].ma = max(bit[id].ma, ma); bit[id].lmi = max(bit[id].lmi, ma); bit[id].lma = max(bit[id].lma, ma); } void dec(int id, int mi){ bit[id].mi = min(bit[id].mi, mi); bit[id].ma = min(bit[id].ma, mi); bit[id].lmi = min(bit[id].lmi, mi); bit[id].lma = min(bit[id].lma, mi); } void down(int id, int l, int r){ if (l == r) return; if (bit[id].lmi != oo){ dec(id * 2, bit[id].lmi); dec(id * 2 + 1, bit[id].lmi); } if (bit[id].lma != -oo){ add(id * 2, bit[id].lma); add(id * 2 + 1, bit[id].lma); } bit[id].lmi = oo; bit[id].lma = -oo; } void ud(int id, int l, int r, int u, int v, int t, int val){ if (l > v || r < u) return; if (l >= u && r <= v){ if (t != 1) dec(id, val); else add(id, val); return; } int mid = (l + r) >> 1; down(id, l, r); ud(id * 2, l, mid, u, v, t, val); ud(id * 2 + 1, mid + 1, r, u, v, t, val); bit[id].mi = min(bit[id * 2].mi, bit[id * 2 + 1].mi); bit[id].ma = max(bit[id * 2].ma, bit[id * 2 + 1].ma); } void go(int id, int l, int r){ if (l == r){ res[l] = bit[id].mi; return; } down(id, l, r); int mid = (l + r) >> 1; go(id * 2, l, mid); go(id * 2 + 1, mid + 1, r); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { bit.resize(4 * n + 1); for (int i = 0; i < k; i++){ ud(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]); } go(1, 1, n); for (int i = 1; i <= n; i++) finalHeight[i - 1] = res[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...