Submission #544658

#	Time	Username	Problem	Language	Result	Execution time	Memory
544658		leaked	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	14 / 100	506 ms	217660 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];
int tt=1;
struct segtree{
    ll t[20*N],p[20*N];
    int l[20*N],r[20*N];
    ll d1,d2;
    segtree(){
        t[0]=0;
        fill(t,t+20*N,0);
        fill(l,l+20*N,0);
        fill(r,r+20*N,0);
        fill(p,p+20*N,0);
    }
    void push(int v,int tl,int tr){
        if(!p[v])
            return;
        if(!l[v]) l[v]=tt++;
        if(!r[v]) r[v]=tt++;
        assert(tt<20*N);
        for(auto &u : {l[v],r[v]})
            p[u]+=p[v],t[u]+=p[v];
        p[v]=0;
        return;
    }
    void upd(int i,ll x,int &v,int tl=0,int tr=N-1){
        if(!v)
            v=tt++;
        assert(tt<20*N);
        if(tl==tr){
            t[v]=x;
            return;
        }
        int tm=(tl+tr)>>1;push(v,tl,tr);
        if(tm>=i)
            upd(i,x,l[v],tl,tm);
        else
            upd(i,x,r[v],tm+1,tr);
        t[v]=min(t[l[v]],t[r[v]]);
    }
    ll get(int l1,int r1,int v,int tl=0,int tr=N-1){
        if(!v || tl>r1 || tr<l1)
            return 0;
        if(tl>=l1&&tr<=r1)
            return t[v];
        int tm=(tl+tr)>>1;push(v,tl,tr);
        return min(get(l1,r1,l[v],tl,tm),get(l1,r1,r[v],tm+1,tr));
    }
    int mg(int v,int u,int tl,int tr){
        if(!v && !u)
            return 0;
        if(tl==tr){
            umin(d1,t[v]);umin(d2,t[u]);
            if(!v){
                t[u]=d1+d2;
                return u;
            }
            t[v]=d1+d2;
            return v;
        }

        if(!v){
            umin(d2,t[u]);
            p[u]+=d1;
            t[u]+=d1;
            return u;
        }
        if(!u){
            umin(d1,t[v]);
            p[v]+=d2;
            t[v]+=d2;
            return v;
        }
        int tm=(tl+tr)>>1;
        if(l[u] || r[u]) push(u,tl,tr);
        if(l[v] || r[v]) push(v,tl,tr);
        p[v]=p[u]=0;
        r[v]=mg(r[v],r[u],tm+1,tr);
        l[v]=mg(l[v],l[u],tl,tm);
        t[v]=d1+d2;
        return v;
    }
    int Merge(int v,int u){
        d1=d2=0;
        return mg(v,u,0,N-1);
    }
}sega;
ll toadd=0;
//map<int,ll> mp;
int root[N];

void dfs(int v){
//    cout<<"DFS "<<v<<endl;
    for(auto &z : g[v]){
        dfs(z);
        root[v]=sega.Merge(root[v],root[z]);
//        cerr<<"EBAL "<<root[v]<<endl;
    }
//    cout<<"W "<<root[v]<<endl;
//    cout<<sega.get(roo)
//    cout<<"HEY "<<sega.get(root[v],h[v],N-1)<<endl;
    sega.upd(h[v],sega.get(h[v],N-1,root[v])-c[v],root[v]);
}
signed main(){
    fast_resp;
    int n;
    cin>>n;
    vec<int>kek;
    ll sm=0;
    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]);sm+=c[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();
    dfs(0);
    cout<<sm+sega.get(0,N-1,root[0]);
    return 0;
}
/*
3
1 3 6
1 2 5
1 5 6
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
2
1 89 964898447
2 20 952129455
*/

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