Submission #761203

#TimeUsernameProblemLanguageResultExecution timeMemory
761203coloboxxWall (IOI14_wall)C++17
8 / 100
442 ms262144 KiB
#include "wall.h" // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define ll long long #define point pair<int, int> #define X first #define Y second #define all(x) (x).begin(), (x).end() #define pb push_back #define show(x) cerr << (#x) << " = " << x << '\n' #define print(x) if (1) {cerr << (#x) << " = "; for (auto it : x) \ cerr << it << ' '; cerr << '\n';} #define fast_io ios_base::sync_with_stdio(0), cin.tie(0) const int N = 1 << 21; const int K = 1 << 19; const int S = 1e7 + 64; const int INF = 2e9 + 64; const ll MAX = 2e18 + 64; const int LOG = 21; const int MOD = 1e9 + 7; //998244353; const int P = 79; using namespace std; vector<point> t[4 * N]; template <class T, T (*F) (T, T)> struct segtree{ int n; T def{}; vector<T> t; segtree(int n, T def, vector<T> v = {}) : n(n), def(def) { t.assign(2 * n, def); for (int i = 0; i < min(n, (int)v.size()); ++i) t[i + n] = v[i]; for (int i = n - 1; i > 0; --i) t[i] = F(t[i << 1], t[i << 1 | 1]); } void update(int p, T val) { for (t[p += n] = val; p > 1; p >>= 1) t[p >> 1] = F(t[p], t[p ^ 1]); } T query(int l, int r) { T res = def; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = F(res, t[l++]); if (r & 1) res = F(res, t[--r]); } return res; } }; int type[N]; void add_segment(int v, int tl, int tr, int l, int r, int op, int id) { if (max(l, tl) > min(r, tr)) return; if (l <= tl && r >= tr) { t[v].pb({op, id}); return; } int tm = (tl + tr) >> 1; add_segment(v << 1, tl, tm, l, r, op, id); add_segment(v << 1 | 1, tm + 1, tr, l, r, op, id); } int Min(int x, int y) { return min(x, y); } int Max(int x, int y) { return max(x, y); } segtree<int, &Min> tmin(K, INF); segtree<int, &Max> tmax(K, -INF); int a[N], ans[N]; int norm(int l, int r, int x) { if (x < l) return l; if (x > r) return r; return x; } int n, k; void dfs(int v, int tl, int tr, int mx_id = -INF) { // show(v); for (auto [op, id] : t[v]) { mx_id = max(mx_id, id); if (type[id] == 2) tmin.update(id, op); else tmax.update(id, op); } if (tl == tr) { // show(tl); if (mx_id == -INF) { ans[tl] = 0; } else { //cerr << "AAA\n"; int lb = -1, rb = mx_id; // show(mx_id); while (lb + 1 < rb) { int mid = (lb + rb) >> 1; int l = tmax.query(mid, mx_id); int r = tmin.query(mid, mx_id); (l <= r ? rb : lb) = mid; } int pos = rb; int l = tmax.query(pos, mx_id); int r = tmin.query(pos, mx_id); // show(l), show(r); if (pos == 0) ans[tl] = norm(l, r, a[tl]); else { int pl = tmax.query(pos - 1, pos - 1); int pr = tmin.query(pos - 1, pos - 1); assert(max(l, pl) > min(r, pr)); // show(pl), show(pr); if (pr < l) ans[tl] = l; else ans[tl] = r; } //cerr << "BBB\n"; } // for (int j = 0; j < k; ++j) // cerr << "{" << tmax.query(j, j) << ", " << tmin.query(j, j) << "}\n"; } else { int tm = (tl + tr) >> 1; dfs(v << 1, tl, tm, mx_id); dfs(v << 1 | 1, tm + 1, tr, mx_id); } for (auto [op, id] : t[v]) { mx_id = max(mx_id, id); if (type[id] == 2) tmin.update(id, INF); else tmax.update(id, -INF); } } void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[]) { n = _n, k = _k; for (int i = 0; i < k; ++i) { type[i] = op[i]; add_segment(1, 0, n - 1, left[i], right[i], height[i], i); } dfs(1, 0, n - 1); for (int i = 0; i < n; ++i) finalHeight[i] = ans[i]; } // int main() // { // int n; // int k; // // for (int i = 0; i < 10; ++i) // // show(tmin.query(i, i)); // // show(tmin.def); // int i, j; // int status = 0; // status = scanf("%d%d", &n, &k); // assert(status == 2); // int* op = (int*)calloc(sizeof(int), k); // int* left = (int*)calloc(sizeof(int), k); // int* right = (int*)calloc(sizeof(int), k); // int* height = (int*)calloc(sizeof(int), k); // int* finalHeight = (int*)calloc(sizeof(int), n); // for (i = 0; i < k; i++){ // status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]); // assert(status == 4); // } // buildWall(n, k, op, left, right, height, finalHeight); // for (j = 0; j < n; j++) // printf("%d\n", finalHeight[j]); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...