Submission #531495

#TimeUsernameProblemLanguageResultExecution timeMemory
531495jesus_coconutWall (IOI14_wall)C++17
0 / 100
160 ms8484 KiB
#include <bits/stdc++.h> #include "wall.h" #define F first #define S second using namespace std; using pii = pair<int, int>; int const inf = (1 << 28); int const N = (1 << 4); struct Item { int mx = inf, mx2 = inf; int mn = -inf, mn2 = -inf; }; struct SegTree { Item values[2 * N]; pii lazy[2 * N]; pii const NO = {inf, -inf}; Item merge(Item const &a, Item const &b) { Item ret; ret.mx = max(a.mx, b.mx); if (a.mx == b.mx) ret.mx2 = max(a.mx2, b.mx2); else { if (a.mx < b.mx) ret.mx2 = max(a.mx, b.mx2); else ret.mx2 = max(a.mx2, b.mx); } ret.mn = min(a.mn, b.mn); if (a.mn == b.mn) ret.mn2 = min(a.mn2, b.mn2); else { if (a.mn > b.mn) ret.mn2 = min(a.mn, b.mn2); else ret.mn2 = min(a.mn2, b.mn); } return ret; } Item updSing(Item a, pii const &b) { if (a.mx == a.mn) { if (b.F < a.mx) { a.mx = a.mn = b.F; } else if (b.S > a.mn) { a.mx = a.mn = b.S; } return a; } a.mx = min(a.mx, b.F); a.mn = max(a.mn, b.S); return a; } pii updSing(pii const &a, pii const &b) { pii ret; ret.F = min(a.F, b.F); ret.S = max(a.S, b.S); if (ret.F < ret.S) { ret.F = ret.S = (ret.F == b.F ? b.F : b.S); } return ret; } void upd(int l, int r, pii ud, int ver, int lx, int rx) { propagate(ver, lx, rx); if (rx <= l || r <= lx || (ud.F >= values[ver].mx && ud.S <= values[ver].mn)) return; if (l <= lx && rx <= r && (ud.F > values[ver].mx2 || ud.S < values[ver].mn2)) { values[ver] = updSing(values[ver], ud); lazy[ver] = updSing(lazy[ver], ud); return; } int M = (lx + rx) / 2; upd(l, r, ud, ver * 2 + 1, lx, M); upd(l, r, ud, ver * 2 + 2, M, rx); values[ver] = merge(values[2 * ver + 1], values[2 * ver + 2]); } void propagate(int ver, int lx, int rx) { if (rx - lx == 1 || lazy[ver] == NO) return; for (int i : {1, 2}) { values[2 * ver + i] = updSing(values[2 * ver + i], lazy[ver]); lazy[2 * ver + i] = updSing(lazy[2 * ver + i], lazy[ver]); } lazy[ver] = NO; } void upd(int l, int r, pii ud) { upd(l, r, ud, 0, 0, N); } void propAll(int ver = 0, int lx = 0, int rx = N) { propagate(ver, lx, rx); if (rx - lx > 1) { int m = (lx + rx) / 2; propAll(2 * ver + 1, lx, m); propAll(2 * ver + 2, m, rx); } } SegTree() { fill(values, values + 2 * N, Item{0, -inf, 0, inf}); fill(lazy, lazy + 2 * N, NO); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ SegTree st; for (int i = 0; i < k; ++i) { pii ud{inf, -inf}; if (op[i] == 1) ud.S = height[i]; else ud.F = height[i]; st.upd(left[i], right[i] + 1, ud); } st.propAll(); for (int i = 0; i < n; ++i) { finalHeight[i] = st.values[N - 1 + i].mx; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...