Submission #1057531

#TimeUsernameProblemLanguageResultExecution timeMemory
1057531erray송신탑 (IOI22_towers)C++17
0 / 100
584 ms112576 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "debug.h" #else #define debug(...) void(37) #endif constexpr int max_D = int(1e9) + 1; template<typename T, typename F = function<T(const T&, const T&)>> struct SparseTable { vector<vector<T>> table; int n; F op; SparseTable () {} SparseTable(vector<T> a, F _op) : op(_op) { n = int(a.size()); int lg = __lg(n) + 1; table.resize(lg + 1); table[0] = a; for (int l = 1; l < lg; ++l) { int s = n - (1 << l) + 1; table[l].resize(s); for (int i = 0; i < s; ++i) { table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << (l - 1))]); } } } T get(int l, int r) { int lg = __lg(r - l + 1); return op(table[lg][l], table[lg][r - (1 << lg) + 1]); } }; constexpr int MAX_NODES = int(2e5) * 20 * 8; int max_N = int(1e5); namespace PST { int t = 0; struct info { int first_id, last_id; int ct; info() { } void init() { first_id = -1, last_id = -1; ct = 0; } }; info I() { static info res; res.init(); return res; } info unite(info l, info r) { info res; res.first_id = (l.first_id == -1 ? r.first_id : l.first_id); res.last_id = (r.last_id == -1 ? l.last_id : r.last_id); res.ct = l.ct + r.ct; return res; } struct node { int L, R; info i; void init() { L = R = -1; i.init(); } void dupe(const node& x) { L = x.L, R = x.R; i = x.i; } }; node tree[MAX_NODES]; int new_node() { tree[t].init(); t++; return t - 1; } void pull(int v) { tree[v].i = unite(tree[v].L == -1 ? I() : tree[tree[v].L].i, tree[v].R == -1 ? I() : tree[tree[v].R].i); } int modify(int v, int l, int r, int p, int x) { int new_v = new_node(); if (v != -1) { tree[new_v].dupe(tree[v]); } else { tree[new_v].init(); } v = new_v; if (l == r) { tree[v].i.last_id = tree[v].i.first_id = x; tree[v].i.ct = (x != -1); return v; } int mid = (l + r) >> 1; if (p <= mid) { tree[v].L = modify(tree[v].L, l, mid, p, x); } else { tree[v].R = modify(tree[v].R, mid + 1, r, p, x); } pull(v); //debug("pull", v, l, r, tree[v].i.ct, tree[v].i.first_id, tree[v].i.last_id); return v; } info get(int v, int l, int r, int ll, int rr) { //debug(v, l, r, tree[v].i.ct, tree[v].i.first_id, tree[v].i.last_id); if (l >= ll && rr >= r) { return tree[v].i; } int mid = (l + r) >> 1; info res; res.init(); if (ll <= mid && tree[v].L != -1) { res = unite(res, get(tree[v].L, l, mid, ll, rr)); } if (mid < rr && tree[v].R != -1) { res = unite(res, get(tree[v].R, mid + 1, r, ll, rr)); } return res; } int modify(int tree_id, int p, int v) { return modify(tree_id, 0, max_N, p, v); } array<int, 3> get_ids(int tree_id, int l, int r) { auto i = get(tree_id, 0, max_N, l, r); return {i.first_id, i.last_id, i.ct}; } }; int N, LG, root; vector<int> H, L, R, tour, tin, tout; SparseTable<int> min_H, max_H, lca_st; int get_lca(int v, int u) { debug(v, u, tin[v], tout[v], tin[u], tout[u]); if (tin[v] > tin[u]) { swap(v, u); } if (tout[v] >= tout[u]) { return v; } return lca_st.get(tout[v], tin[u]); } int S; vector<int> times, segtrees; int get_time(int x) { assert(times[0] <= x); return int(lower_bound(times.begin(), times.end(), x + 1) - times.begin()) - 1; } void init(int _N, std::vector<int> _H) { debug("hello?"); N = _N; H = _H; LG = __lg(N) + 1; vector<int> foo(N); iota(foo.begin(), foo.end(), 0); min_H = SparseTable<int>(foo, [&](int x, int y) { return (H[x] < H[y] ? x : y); }); max_H = SparseTable<int>(foo, [&](int x, int y) { return (H[x] > H[y] ? x : y); }); vector<vector<int>> g(N); L.resize(N), R.resize(N), tin.resize(N), tout.resize(N); vector<int> par(N, -1); vector<int> mn(N); iota(mn.begin(), mn.end(), 0); auto Dfs = [&](int l, int r, auto&& Dfs) -> int { int v = max_H.get(l, r); tin[v] = int(tour.size()); tour.push_back(v); L[v] = l, R[v] = r; if (l != v) { g[v].push_back(Dfs(l, v - 1, Dfs)); } if (r != v) { g[v].push_back(Dfs(v + 1, r, Dfs)); } for (auto u : g[v]) { if (H[mn[u]] < H[mn[v]]) mn[v] = mn[u]; mn[v] = min(mn[v], mn[u]); par[u] = v; tour.push_back(v); } tout[v] = int(tour.size()) - 1; return v; }; root = Dfs(0, N - 1, Dfs); debug(L, R); lca_st = SparseTable<int>(tour, [&](int x, int y) { return H[x] > H[y] ? x : y; }); vector<int> act_t(N), dis_t(N); for (int i = 0; i < N; ++i) { act_t[i] = H[i] - H[mn[i]] + 1; } for (int i = 0; i < N; ++i) { int p = par[i]; dis_t[i] = (p == -1 ? max_D : H[p] - H[mn[i]] + 1); } debug(act_t, dis_t); // each segment is active in the range [act_t_i, dis_t_i) for (int i = 0; i < N; ++i) { times.push_back(act_t[i]); times.push_back(dis_t[i]); } sort(times.begin(), times.end()); times.erase(unique(times.begin(), times.end()), times.end()); S = int(times.size()); vector<vector<int>> updates(S); for (int i = 0; i < N; ++i) { updates[get_time(dis_t[i])].push_back(~i); updates[get_time(act_t[i])].push_back(i); } int segtree = PST::new_node(); for (int i = 0; i < S; ++i) { for (auto x : updates[i]) { int val, ind; if (x < 0) { ind = mn[~x]; val = -1; } else { ind = mn[x]; val = mn[x]; } debug(ind, val, L[ind], R[ind]); segtree = PST::modify(segtree, ind, val); } //debug(i, segtree); segtrees.push_back(segtree); } } int max_towers(int QL, int QR, int D) { int t = get_time(D); auto[l, r, ct] = PST::get_ids(segtrees[t], QL, QR); int prev_id = (QL > 0 ? PST::get_ids(segtrees[t], 0, QL - 1)[1] : -1); int next_id = (QR < N - 1 ? PST::get_ids(segtrees[t], QR + 1, N - 1)[0] : -1); debug(l, r, prev_id, next_id); if (l == -1) { if (prev_id == -1 || next_id == -1) { return 1; } int lca = get_lca(prev_id, next_id); assert(l <= lca && r <= lca); if (QL < lca && lca < QR && H[lca] - max(H[min_H.get(QL, lca)], H[min_H.get(lca, QR)]) >= D) { return 2; } else { return 1; } } else { if (prev_id != -1) { int lca = get_lca(prev_id, l); debug(lca); if (QL < lca && H[lca] - max(H[l], H[min_H.get(QL, lca)]) >= D) { ct++; } } if (next_id != -1) { int lca = get_lca(r, next_id); if (lca < QR && H[lca] - max(H[min_H.get(lca, QR)], H[r]) >= D) { ct++; } } return ct; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...