제출 #1258684

#제출 시각아이디문제언어결과실행 시간메모리
1258684biankTree (IOI24_tree)C++20
41 / 100
2094 ms27036 KiB
#include "tree.h" #include <bits/stdc++.h> #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define forn(i, n) forsn(i, 0, n) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define dforn(i, n) dforsn(i, 0, n) #define sz(x) int(x.size()) #define all(x) begin(x), end(x) #define pb push_back #define eb emplace_back #define fst first #define snd second using namespace std; using vi = vector<int>; using ii = pair<int, int>; using ll = long long; const int INF = 1e9 + 20; template<typename T, T (*op)(const T&, const T&), T (*id)()> struct SegTree { int n; vector<T> st; SegTree(int _n = 0) : n(_n), st(2 * n, id()) {}; void init(vector<T> v) { assert(sz(v) == n); forn(i, n) st[i + n] = v[i]; dforsn(i, 1, n) st[i] = op(st[2 * i], st[2 * i + 1]); } T query(int l, int r) { T lans = id(), rans = id(); for (l += n, r += n; l < r; l /= 2, r /= 2) { if (l & 1) lans = op(lans, st[l++]); if (r & 1) rans = op(st[--r], rans); } return op(lans, rans); } void updateSet(int p, T v) { st[p += n] = v; while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]); } void updateAdd(int p, T v) { p += n; st[p] = op(st[p], v); while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]); } }; const int MAX_N = 2e5 + 9; int in[MAX_N], out[MAX_N]; int w[MAX_N], t; vi adj[MAX_N]; int n; void dfs(int u) { in[u] = t++; for (int v : adj[u]) dfs(v); out[u] = t; } void init(vi P, vi W) { n = sz(P); forsn(i, 1, n) adj[P[i]].pb(i); forn(i, n) w[i] = W[i]; t = 0; dfs(0); } ii minOp(const ii &a, const ii &b) { return min(a, b); } ii minNeutr() { return ii{INF, INF}; } template<typename T> T sumOp(const T &a, const T &b) { return a + b; } template<typename T> T sumNeutr() { return 0; } ll query(int L, int R) { SegTree<ii, minOp, minNeutr> mini(n); vector<ii> a(n); forn(u, n) a[in[u]] = {w[u], u}; mini.init(a); SegTree<ll, sumOp, sumNeutr> sum(n); SegTree<int, sumOp, sumNeutr> cnt(n + 1); ll ret = 0LL; dforn(u, n) { if (adj[u].empty()) { sum.updateAdd(in[u], L); mini.updateSet(in[u], minNeutr()); ret += 1LL * w[u] * L; continue; } ll currSum = sum.query(in[u], out[u]); while (currSum > R) { auto [_, v] = mini.query(in[u], out[u]); if (cnt.query(0, in[v] + 1) > 0) { mini.updateSet(in[v], minNeutr()); continue; } ll sumV = sum.query(in[v], out[v]); ll need = min(currSum - R, sumV - L); currSum -= need; sum.updateAdd(in[v], -need); ret += 1LL * w[v] * need; if (sumV - need == L) { cnt.updateAdd(in[v], +1); cnt.updateAdd(out[v], -1); } } } return ret; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...