Submission #1160832

#TimeUsernameProblemLanguageResultExecution timeMemory
1160832JahonaliXWall (IOI14_wall)C++17
0 / 100
74 ms8008 KiB
#include <bits/stdc++.h> using namespace std; struct segment_tree { int n; vector<int> mn, mx; segment_tree(int m) { n = m; mn.assign(n << 2, 0); mx.assign(n << 2, 1e9); } void push(int v, int l, int r) { if (l == r) return; mn[v << 1] = min(mn[v << 1], mx[v]); mn[v << 1 | 1] = min(mn[v << 1 | 1], mx[v]); mx[v << 1] = min(mx[v << 1], mx[v]); mx[v << 1 | 1] = min(mx[v << 1 | 1], mx[v]); mn[v << 1] = max(mn[v << 1], mn[v]); mn[v << 1 | 1] = max(mn[v << 1 | 1], mn[v]); mx[v << 1] = max(mx[v << 1], mn[v]); mx[v << 1 | 1] = max(mx[v << 1 | 1], mn[v]); mx[v] = 1e9; mn[v] = 0; } void qmin(int l, int r, int x, int v = 1, int tl = 0, int tr = -1) { if (tr < 0) tr += n; push(v, tl, tr); if (l <= tl && tr <= r) mx[v] = x; else { int m = (l + r) >> 1; if (r <= m) qmin(l, r, x, v << 1, tl, m); if (m < l) qmin(l, r, x, v << 1 | 1, m + 1, tr); } } void qmax(int l, int r, int x, int v = 1, int tl = 0, int tr = -1) { if (tr < 0) tr += n; push(v, tl, tr); if (l <= tl && tr <= r) mn[v] = x; else { int m = (l + r) >> 1; if (r <= m) qmax(l, r, x, v << 1, tl, m); if (m < l) qmax(l, r, x, v << 1 | 1, m + 1, tr); } } int get(int i, int v = 1, int l = 0, int r = -1) { if (r < 0) r += n; push(v, l, r); if (l == r) return mn[v]; int m = (l + r) >> 1; if (i > m) return get(i, v << 1 | 1, m + 1, r); else return get(i, v << 1, l, m); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { segment_tree s(n); for (int i = 0; i < k; ++i) { if (op[i] == 1) s.qmax(left[i], right[i], height[i]); else s.qmin(left[i], right[i], height[i]); } for (int i = 0; i < n; ++i) finalHeight[i] = s.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...