Submission #1198319

#TimeUsernameProblemLanguageResultExecution timeMemory
1198319ansoriTree (IOI24_tree)C++20
48 / 100
2095 ms89628 KiB
#include "tree.h" #include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const ll N = 2e5 + 52; bool chk , oko; ll n; ll ans , sml; vector<int> p , w; vector<ll> g[N] , t(4 * N , 0); priority_queue<pair<ll , ll>> st[N]; ll in[N] , out[N] , tim , kur , sz; set<ll> stp; void update (ll v, ll l, ll r, ll j , ll x) { if(r - l == 1 and l == j) t[v] = x; else { ll m = (l + r) / 2; if (j < m) update (v * 2 , l, m, j , x); else update (v * 2 + 1 , m , r , j , x); t[v] = t[v * 2] + t[v * 2 + 1]; } } void gett(ll v, ll l, ll r , ll l1 , ll r1) { if(l <= l1 and r >= r1) kur += t[v]; else { ll m = (l1 + r1) / 2; if(!(l1 >= r || m <= l)) { gett(v * 2 , l , r , l1 , m); } if(!(m >= r || r1 <= l)) { gett(v * 2 + 1 , l , r , m , r1); } } } void upd(ll p , ll x){ update(1 , 0 , sz , p , x); } ll get(ll l , ll r){ kur = 0; gett(1 , l , r + 1 , 0 , sz); return kur; } ll l , r , sum[N]; void dfs(ll v){ for(auto to : g[v]){ dfs(to); } for(auto to : g[v]){ if(st[to].size() > st[v].size()){ swap(st[v] , st[to]); } while(st[to].size()){ st[v].push(st[to].top()); st[to].pop(); } } st[v].push({-w[v] , v}); upd(in[v] , 0); if(g[v].size() == 0){ upd(in[v] , l); stp.erase(in[v]); return ; } while(get(in[v] , out[v]) > r){ auto u = st[v].top().se; auto ww = st[v].top().fi; st[v].pop(); if(stp.find(in[u]) == stp.end()){ continue ; } ll val = min(get(in[u] , out[u]) - l , get(in[v] , out[v]) - r); ans += val * (-ww); upd(in[u] , get(in[u] , in[u]) - val); if(get(in[u] , out[u]) == l){ while(stp.lower_bound(in[u]) != stp.end() and (*stp.lower_bound(in[u])) <= out[u]){ stp.erase(stp.lower_bound(in[u])); } } else st[v].push({ww , u}); } } void dsfs(int v){ for(auto to : g[v]){ dsfs(to); sum[v] += sum[to]; } sum[v] = max(sum[v] , l); if(oko){ ans += max(0ll , sum[v] - r) * w[v]; sum[v] = min(sum[v] , r); return ; } } void dffs(ll v){ in[v] = (++ tim); for(auto to : g[v]){ dffs(to); } out[v] = tim; } void init(std::vector<int> P, std::vector<int> W) { p = P , w = W; n = p.size(); chk = 1; oko = 1; for(ll i = 0;i < n; ++ i){ if(w[i] != 1) chk = false; if(i) g[p[i]].push_back(i); if(i) oko &= (w[p[i]] <= w[i]); } for(ll i = 0;i < n; ++ i){ if(g[i].size() == 0){ sml += w[i]; } } tim = -1; dffs(0); sz = n; } long long query(int L, int R) { ans = 0; l = L; r = R; if(! chk){ ans += L * sml; if(oko){ for(int i = 0;i < n; ++ i) sum[i] = 0; dsfs(0); return ans; } while(st[0].size()) st[0].pop(); for(ll i = 0;i < n; ++ i) stp.insert(i); dfs(0); } else{ //cout << sml << ' '; ans = L * sml + max(0ll , L * sml - R); } return ans; }
#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...