Submission #1198308

#TimeUsernameProblemLanguageResultExecution timeMemory
1198308ansori트리 (IOI24_tree)C++20
38 / 100
2100 ms248624 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]; priority_queue<pair<ll , ll>> st[N]; ll in[N] , out[N] , tim; set<ll> stp; class segtree { public : ll sz; ll kur; vector<ll> t; segtree (ll n) : sz(n * 2) , kur(0) , t(vector<ll> (n * 4 , 0)) { } 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; void dfs(ll v , segtree & t){ for(auto to : g[v]){ dfs(to , t); } ll u = v; for(auto to : g[v]){ if(oko) continue ; 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}); t.upd(in[v] , 0); if(g[v].size() == 0){ t.upd(in[v] , l); stp.erase(in[v]); return ; } if(oko){ ll val = max(0ll , t.get(in[v] , out[v]) - r); ans += w[v] * val; t.upd(in[v] , -val); return ; } while(t.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 ; } //cout << u << ' ' << ww << '\n'; ll val = min(t.get(in[u] , out[u]) - l , t.get(in[v] , out[v]) - r); //cout << val << ' '; ans += val * (-ww); t.upd(in[u] , t.get(in[u] , in[u]) - val); //cout << t.get(in[u] , out[u]) << ' '; if(t.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}); } //cout << v << ' ' << ans << '\n'; } 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; bool oko = true; for(ll i = 0;i < n; ++ i){ if(w[i] != 1) chk = false; if(i) g[p[i]].push_back(i); if(w[i] < w[p[i]]) oko = false; } for(ll i = 0;i < n; ++ i){ if(g[i].size() == 0){ sml += w[i]; } } tim = -1; dffs(0); } long long query(int L, int R) { ans = 0; l = L; r = R; if(! chk){ ans += L * sml; while(st[0].size()) st[0].pop(); for(ll i = 0;i < n; ++ i) stp.insert(i); segtree t(n); dfs(0 , t); } 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...