Submission #544580

#	Time	Username	Problem	Language	Result	Execution time	Memory
544580		leaked	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	5 ms	6612 KiB

worst_reporter2

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
const ll inf=1e18;
vec<int> g[N];
int c[N],a[N],h[N];
struct fenwick{
    ll fnw[N];
    fenwick(){
        fill(fnw,fnw+N,0);
    }
    void upd(int i,ll x){
        ++i;
        while(i<N){
            fnw[i]+=x;
            i+=i&-i;
        }
    }
    ll get(int i){
        ++i;
        ll ans=0;
        while(i>0){
            ans+=fnw[i];
            i-=i&-i;
        }
        return ans;
    }
}fen;
map<int,ll> mp;
vec<pil> *dps[N];
int dp[N];
void dfs1(int v){
    dp[v]=1;
    for(auto &z : g[v]){
        dfs1(z);
        dp[v]+=dp[z];
    }
}
void dfs(int v,bool keep=0){
//    for(int i=0;i<N;i++){
//        dp[v][i]=(h[v]==i?0:c[v]);
//    }
//    cout<<"DFS "<<v<<' '<<h[v]<<endl;
    int big=-1;
    for(auto &z : g[v]){
        if(big==-1 || dp[z]>dp[big])
            big=z;
    }
    for(auto &z : g[v]){
        if(z==big) continue;
        dfs(z,0);
    }
    if(big!=-1){
        dfs(big,1);
        dps[v]=dps[big];
    }
    else{
        dps[v]=new vec<pil>();
    }

    for(auto &z : g[v]){
        if(z==big) continue;
        for(auto &u : *dps[z]){
            mp[u.f]+=u.s;
            fen.upd(u.f,u.s);
        }
        (*dps[z]).clear();
    }
    if(h[v]!=0){
        fen.upd(0,c[v]);mp[0]+=c[v];
        mp[h[v]]-=c[v];fen.upd(h[v],-c[v]);
    }else mp[h[v]]=0;
    mp[h[v]+1]+=c[v];fen.upd(h[v]+1,c[v]);

    auto it=mp.lower_bound(h[v]);
    vec<pil> del;
    ll myval=fen.get(h[v]);
    while(it!=mp.begin()){
        --it;
        if(fen.get(it->f)>=myval)
            del.pb(*it);
        else break;
    }
//    for(auto &z : mp)
//        cout<<"DP1 "<<v<<' '<<z.f<<' '<<fen.get(z.f)<<endl;

    reverse(all(del));
    for(auto &z : del){
        ll dt=myval-fen.get(z.f);
        fen.upd(z.f,dt);
//        cout<<"CHECK "<<z.f<<' '<<fen.get(z.f)<<' '<<myval<<endl;
        mp[z.f]+=dt;
        if(mp[z.f]==0)
            mp.erase(z.f);
    }
    {
        ll dt=myval-fen.get(h[v]);
        fen.upd(h[v],dt);
        mp[h[v]]+=dt;
    }
//    for(auto &z : del)
//        mp.erase(z.f),fen.upd(z.f,-z.s);
//    for(auto &z : mp)
//        cout<<"DP "<<v<<' '<<z.f<<' '<<fen.get(z.f)<<endl;
    if(!keep){
        for(auto &u : mp)
            fen.upd(u.f,-u.s),(*dps[v]).pb(u);
        mp.clear();
    }
//    f
}
signed main(){
    fast_resp;
    int n;
    cin>>n;
    vec<int>kek;
    for(int i=0;i<n;i++){
        cin>>a[i]>>h[i]>>c[i];--a[i];
        if(a[i]!=i) g[a[i]].pb(i);
        kek.pb(h[i]);
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin();
    dfs1(0);dfs(0);
    cout<<(*dps[0])[0].s;
    return 0;
}
/*
2
1 89 964898447
2 20 952129455
*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21