Submission #531482

#TimeUsernameProblemLanguageResultExecution timeMemory
531482tkwiatkowskiWall (IOI14_wall)C++17
32 / 100
3067 ms27032 KiB
/* Zadanie: Wall Autor: Tomasz Kwiatkowski */ #include <bits/stdc++.h> #include "wall.h" #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; struct segTree { vector<pair<int, int>> t_min; vector<pair<int, int>> lazy; vector<pair<int, int>> t_max; int BASE; segTree(int n) { BASE = 1; while (BASE <= n) BASE *= 2; t_min.resize(2*BASE + 7, {1e9, 0}); t_max.resize(2*BASE + 7, {0, 0}); lazy.resize(2*BASE + 7, {-1, 0}); for (int i = 0; i < BASE; ++i) t_min[BASE + i] = t_max[BASE + i] = {0, i}; for (int i = BASE - 1; i > 0; --i) { t_min[i] = min(t_min[2*i], t_min[2*i + 1]); t_max[i] = max(t_max[2*i], t_max[2*i + 1]); } } void Update(int v) { if (lazy[v].fi == -1) return; t_min[2*v] = t_max[2*v] = lazy[v]; t_min[2*v + 1] = t_max[2*v + 1] = lazy[v]; lazy[2*v] = lazy[2*v + 1] = lazy[v]; lazy[v] = {-1, 0}; } void Set(int a, int b, pair<int, int> val, int v = 1, int l = 0, int r = -1) { if (r == -1) r = BASE - 1; if (b < l || r < a) return; if (a <= l && r <= b) { t_min[v] = t_max[v] = val; lazy[v] = val; return; } int mid = (l + r)/2; Update(v); Set(a, b, val, 2*v, l, mid); Set(a, b, val, 2*v + 1, mid + 1, r); t_min[v] = min(t_min[2*v], t_min[2*v + 1]); t_max[v] = max(t_max[2*v], t_max[2*v + 1]); } pair<int, int> Min(int a, int b, int v = 1, int l = 0, int r = -1) { if (r == -1) r = BASE - 1; if (b < l || r < a) return {1e9, 0}; if (a <= l && r <= b) return t_min[v]; int mid = (l + r)/2; Update(v); auto res_l = Min(a, b, 2*v, l, mid); auto res_r = Min(a, b, 2*v + 1, mid + 1, r); t_min[v] = min(t_min[2*v], t_min[2*v + 1]); t_max[v] = max(t_max[2*v], t_max[2*v + 1]); return min(res_l, res_r); } pair<int, int> Max(int a, int b, int v = 1, int l = 0, int r = -1) { if (r == -1) r = BASE - 1; if (b < l || r < a) return {0, 0}; if (a <= l && r <= b) return t_max[v]; int mid = (l + r)/2; Update(v); auto res_l = Max(a, b, 2*v, l, mid); auto res_r = Max(a, b, 2*v + 1, mid + 1, r); t_min[v] = min(t_min[2*v], t_min[2*v + 1]); t_max[v] = max(t_max[2*v], t_max[2*v + 1]); return max(res_l, res_r); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { segTree h(n); segTree lt(n), rt(n); lt.Set(0, n - 1, {0, 0}); rt.Set(0, n - 1, {n - 1, 0}); for (int i = 0; i < k; ++i) { if (op[i] == 1) { auto res = h.Min(left[i], right[i]); while (res.fi < height[i]) { int l = lt.Min(res.se, res.se).fi; int r = rt.Min(res.se, res.se).fi; if (l < left[i]) { rt.Set(l, left[i] - 1, {left[i] - 1, 0}); l = left[i]; } if (r > right[i]) { lt.Set(right[i] + 1, r, {right[i] + 1, 0}); h.Set(right[i] + 1, r, {res.fi, right[i] + 1}); r = right[i]; } h.Set(l, r, {height[i], l}); if (h.Max(l - 1, l - 1).fi == height[i]) l = lt.Min(l - 1, l - 1).fi; if (h.Max(r + 1, r + 1).fi == height[i]) r = rt.Min(r + 1, r + 1).fi; lt.Set(l, r, {l, 0}); rt.Set(l, r, {r, 0}); res = h.Min(left[i], right[i]); } } else { auto res = h.Max(left[i], right[i]); while (res.fi > height[i]) { int l = lt.Min(res.se, res.se).fi; int r = rt.Min(res.se, res.se).fi; if (l < left[i]) { rt.Set(l, left[i] - 1, {left[i] - 1, 0}); l = left[i]; } if (r > right[i]) { lt.Set(right[i] + 1, r, {right[i] + 1, 0}); h.Set(right[i] + 1, r, {res.fi, right[i] + 1}); r = right[i]; } h.Set(l, r, {height[i], l}); if (h.Max(l - 1, l - 1).fi == height[i]) l = lt.Min(l - 1, l - 1).fi; if (h.Max(r + 1, r + 1).fi == height[i]) r = rt.Min(r + 1, r + 1).fi; lt.Set(l, r, {l, 0}); rt.Set(l, r, {r, 0}); res = h.Max(left[i], right[i]); } } } for (int i = 1; i < h.BASE; ++i) h.Update(i); for (int i = 0; i < n; ++i) finalHeight[i] = h.t_max[h.BASE + i].fi; return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...