Submission #1193745

#TimeUsernameProblemLanguageResultExecution timeMemory
1193745tkm_algorithmsWall (IOI14_wall)C++20
100 / 100
742 ms48868 KiB
/** * In the name of Allah * We are nothing and you're everything **/ #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() //const ll inf = 1e18; int* res; struct segtree { vector<pair<int, int>> tree; void init(int n) { int size = 1; while (size < n)size <<= 1; tree.assign(2*size-1, {0, 0}); } void push(int x, int val, int op) { int &l = tree[x].first, &r = tree[x].second; l = (op == 1?max(l, val):min(l, val)); r = (op == 1?max(r, val):min(r, val)); } void apply(int l, int r, int val, int op, int x, int lx, int rx) { if (rx <= l || r <= lx)return; if (lx >= l && rx <= r) { push(x, val, op); res[l] = tree[x].first; return; } int &lo = tree[x].first, &hi = tree[x].second; push(2*x+1, lo, 1); push(2*x+1, hi, 2); push(2*x+2, lo, 1); push(2*x+2, hi, 2); lo = 0, hi = 1e5+5; int m = lx+rx>>1; apply(l, r, val, op, 2*x+1, lx, m); apply(l, r, val, op, 2*x+2, m, rx); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { segtree a; a.init(n); res = finalHeight; for (int i = 0; i < k; ++i) a.apply(left[i], right[i]+1, height[i], op[i], 0, 0, n); for (int i = 0; i < n; ++i) a.apply(i, i+1, 0, 1, 0, 0, n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...