Submission #1094178

#TimeUsernameProblemLanguageResultExecution timeMemory
1094178vladiliusWorst Reporter 4 (JOI21_worst_reporter4)C++17
14 / 100
363 ms524288 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define arr3 array<ll, 3> const ll inf = 1e15; const int N = 2e5; struct DS{ struct node{ node *l, *r; ll x; int s; node(){ l = r = 0; x = s = 0; } }; vector<pair<int, ll>> vv; node *rt; void init(){ rt = new node(); } int size(){ return rt -> s; } void fn(node *v, int tl, int tr){ if (!(v -> s)) return; if (tl == tr){ vv.pb({tl, v -> x}); return; } int tm = (tl + tr) / 2; if (v -> l) fn(v -> l, tl, tm); if (v -> r) fn(v -> r, tm + 1, tr); } void fn(){ vv.clear(); fn(rt, 1, N); } void recalc(node *v){ v -> x = v -> s = 0; if (v -> l){ v -> x += v -> l -> x; v -> s += v -> l -> s; } if (v -> r){ v -> x += v -> r -> x; v -> s += v -> r -> s; } } void add(node *v, int tl, int tr, int& p, ll& x){ if (tl == tr){ v -> x += x; v -> s = 1; return; } int tm = (tl + tr) / 2; if (p <= tm){ if (!(v -> l)) v -> l = new node(); add(v -> l, tl, tm, p, x); } else { if (!(v -> r)) v -> r = new node(); add(v -> r, tm + 1, tr, p, x); } recalc(v); } void add(int l, int r, ll x){ add(rt, 1, N, l, x); r++; x = -x; if (r <= N) add(rt, 1, N, r, x); } void add1(int& p, ll& x){ add(rt, 1, N, p, x); } void clear(node *&v, int tl, int tr, int l, int r){ if (l > tr || r < tl) return; if (l <= tl && tr <= r){ v = 0; return; } int tm = (tl + tr) / 2; if (v -> l) clear(v -> l, tl, tm, l, r); if (v -> r) clear(v -> r, tm + 1, tr, l, r); recalc(v); } void upd(node *v, int tl, int tr, int& p, ll& x){ if (tl == tr){ v -> x = x; v -> s = 1; return; } int tm = (tl + tr) / 2; if (p <= tm){ if (!(v -> l)) v -> l = new node(); upd(v -> l, tl, tm, p, x); } else { if (!(v -> r)) v -> r = new node(); upd(v -> r, tm + 1, tr, p, x); } recalc(v); } void upd(int p, ll x){ upd(rt, 1, N, p, x); } void ch(int l, int r, ll x){ ll S1 = 0, S2 = get(l - 1); if (r < N) S1 = get(r + 1); if (l < r) clear(rt, 1, N, l + 1, r); upd(l, x - S2); if (r < N) upd(r + 1, S1 - x); } ll get(node *v, int tl, int tr, int& l, int& r){ if (l > tr || r < tl) return 0; if (l <= tl && tr <= r) return v -> x; int tm = (tl + tr) / 2; ll out = 0; if (v -> l) out += get(v -> l, tl, tm, l, r); if (v -> r) out += get(v -> r, tm + 1, tr, l, r); return out; } ll get(int p){ if (!p) return 0; int l = 1; return get(rt, 1, N, l, p); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; vector<int> a(n + 1), h(n + 1), c(n + 1), g[n + 1]; for (int i = 1; i <= n; i++){ cin>>a[i]>>h[i]>>c[i]; if (a[i] != i) g[a[i]].pb(i); } vector<pii> all; for (int i = 1; i <= n; i++) all.pb({h[i], i}); sort(all.begin(), all.end()); int i = 0, cc = 0; while (i < all.size()){ int j = i; while (j < all.size() && all[i] == all[j]){ j++; } cc++; while (i < j){ h[all[i].ss] = cc; i++; } } DS T[n + 1]; vector<vector<ll>> dp(n + 1, vector<ll>(cc + 1)), t(n + 1, vector<ll>(cc + 1)); function<void(int)> solve = [&](int v){ for (int i: g[v]) solve(i); dp[v][h[v]] = 0; for (int x = 1; x <= cc; x++) dp[v][x] = c[v] * (x != h[v]); for (int i: g[v]){ for (int x = 1; x <= cc; x++){ dp[v][x] += t[i][x]; } } t[v][cc] = dp[v][cc]; for (int i = cc - 1; i > 0; i--) t[v][i] = min(t[v][i + 1], dp[v][i]); T[v].init(); for (int i: g[v]){ if (T[v].size() < T[i].size()) swap(T[v], T[i]); T[i].fn(); for (auto [p, x]: T[i].vv){ T[v].add1(p, x); } } if (h[v] > 1) T[v].add(1, h[v] - 1, c[v]); if (h[v] < cc) T[v].add(h[v] + 1, cc, c[v]); ll S1 = T[v].get(h[v]), S2 = (h[v] == cc) ? inf : T[v].get(h[v] + 1); if (S1 < S2 && h[v] > 1 && T[v].get(h[v] - 1) > S1){ int l = 1, r = h[v] - 1; while (l + 1 < r){ int m = (l + r) / 2; ll k = T[v].get(m); if (k <= S1){ l = m + 1; } else { r = m; } } if (T[v].get(l) > S1) r = l; T[v].ch(r, h[v] - 1, S1); } }; solve(1); ll out = 1e15; for (int x = 1; x <= cc; x++) out = min(out, T[1].get(x)); cout<<out<<"\n"; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:151:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     while (i < all.size()){
      |            ~~^~~~~~~~~~~~
worst_reporter2.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         while (j < all.size() && all[i] == all[j]){
      |                ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...