Submission #1207478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207478		segfault_ikuyo	Tree (IOI24_tree)	C++20	0 / 100	66 ms	29608 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back

const int maxn=2e5+5;
const int maxw=1e6+5;
int n,t,u;
int in[maxn],out[maxn],leaf[maxn],ans[maxw],ans2[maxw];
pii cnt[maxn];
vector<pii> ord;
vector<int> adj[maxn];
vector<signed> p,w;

int tree[maxn*4],lazy[maxn];

void pushdown(int l,int r,int idx){
    if(lazy[idx]){
        tree[idx]=lazy[idx];
        if(l!=r){
            tree[idx*2]=lazy[idx];
            tree[idx*2+1]=lazy[idx];
        }
        lazy[idx]=0;
    }
}

void update(int l,int r,int idx,int u,int v,int val){
    pushdown(l,r,idx);
    if(v<l||r<u) return;
    if(u<=l&&r<=v){
        lazy[idx]=val;
        pushdown(l,r,idx);
        return;
    }
    int m=l+((r-l)>>1);
    update(l,m,idx*2,u,v,val);
    update(m+1,r,idx*2+1,u,v,val);
    tree[idx]=max(tree[idx*2],tree[idx*2+1]);
}

int get(int l,int r,int idx,int u,int v){
    pushdown(l,r,idx);
    if(v<l||r<u) return -1;;
    if(u<=l&&r<=v) return tree[idx];
    int m=l+((r-l)>>1);
    return max(get(l,m,idx*2,u,v), get(m+1,r,idx*2+1,u,v));
}

void dfs1(int x){
    in[x]=t++;
    if(!adj[x].size()) leaf[x]=1;
    for(int c:adj[x]){
        dfs1(c);
        leaf[x]+=leaf[c];
    }
    out[x]=t;
}

void init(vector<signed> P,vector<signed> W){
    p=P;w=W;
    n=p.size();
    for(int i=0;i<n;i++){
        if(i) adj[p[i]].pb(i);
        ord.pb({w[i],i});
    }

    sort(ord.begin(),ord.end());
    dfs1(0);
    cnt[leaf[0]]={1,0};
    for(int k=0;k<maxw;k++){
        while(u<n&&ord[u].f<=k){
            int cur=ord[u].s;
            u++;
            int p=get(0,n,1,in[cur],in[cur]);
            // remove parent
            if(cnt[leaf[p]].s!=k) ans[leaf[p]]+=cnt[leaf[p]].f*(k-cnt[leaf[p]].s);
            cnt[leaf[p]].f--;
            cnt[leaf[p]].s=k;
            
            // add parent
            if(p!=cur){
                leaf[p]-=leaf[cur]-1;
                if(cnt[leaf[p]].s!=k) ans[leaf[p]]+=cnt[leaf[p]].f*(k-cnt[leaf[p]].s);
                cnt[leaf[p]].f++;
                cnt[leaf[p]].s=k;
            }

            // add children
            for(int c:adj[cur]){
                update(0,n,1,in[c],out[c]-1,c);
                if(w[c]<k) continue;
                if(cnt[leaf[c]].s!=k) ans[leaf[c]]+=cnt[leaf[c]].f*(k-cnt[leaf[c]].s);
                cnt[leaf[c]].f++;
                cnt[leaf[c]].s=k;
            }

            // for(int i=0;i<10;i++){
            //     cout<<cnt[i].f<<' ';
            // }cout<<'\n';
            // for(int i=0;i<10;i++){
            //     cout<<cnt[i].s<<' ';
            // }cout<<'\n';
            // for(int i=0;i<10;i++){
            //     cout<<ans[i]<<' ';
            // }cout<<'\n';cout<<'\n';
        }
        
    }
    for(int i=1;i<maxw;i++){
        ans2[i]=ans[i]*i;
        ans[i]+=ans[i-1];
        ans2[i]+=ans2[i-1];
    }
}

int query(signed L, signed R) {
    int s=R/L;
    return ans2[maxw-1]*L+(ans2[maxw-1]-ans2[s])*L-(ans[maxw-1]-ans[s])*L;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19