Submission #1230459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230459		moondarkside	Tree (IOI24_tree)	C++20	0 / 100	2097 ms	58536 KiB

tree

#include<bits/stdc++.h>
using namespace std;

#define INFint 1000000000

vector<vector<int>> Children;
vector<int> RangeSize;
vector<pair<int,int>> WeightsSegTree;
vector<long long> ValArray;
vector<int> XtoIndx;

pair<int,int>  setWeightTree(int pos,int l, int r,int n,pair<int,int> value){
    if(pos>r){
        return WeightsSegTree[n];
    }
    if(pos<l){
        return WeightsSegTree[n];
    }
    if(pos==l && l==r){
        WeightsSegTree[n]=value;
        return value;
    }
    pair<int,int> a=setWeightTree(pos,l,(l+r)/2,n*2,value);
    pair<int,int> b=setWeightTree(pos,(l+r)/2+1,r,n*2+1,value);
    if(b<a){
        a=b;
    }
    WeightsSegTree[n]=a;
    return a;
}

int dfs(int x,std::vector<int>& W,int indx){
    int children=1;
    setWeightTree(indx,0,W.size(),1,{W[x],x});
    XtoIndx[x]=indx;
    for(int i=0;i<Children[x].size();i++){
        children+=dfs(Children[x][i],W,indx+children);
    }
    RangeSize[x]=children;
    return children;
}

void init(std::vector<int> P, std::vector<int> W){
    Children=vector<vector<int>>(P.size());
    RangeSize=vector<int>(P.size());
    XtoIndx=vector<int>(P.size());
    WeightsSegTree=vector<pair<int,int>>(6*P.size());
    
    for(int i=1;i<P.size();i++){
        Children[P[i]].push_back(i);
    }
    dfs(0,W,0);
    
}



long long SetValue(int pos,int l, int r,int n,int value){
    if(pos>r){
        return ValArray[n];
    }
    if(pos<l){
        return ValArray[n];
    }
    if(pos==l && l==r){
        ValArray[n]=value;
        return value;
    }
    long long val=SetValue(pos,l,(l+r)/2,n*2,value)+SetValue(pos,(l+r)/2+1,r,n*2+1,value);
    ValArray[n]=val;
    return val;
}

long long GetValueRange(int x,int y,int l, int r,int n){
    if(x>r){
        return 0;
    }
    if(y<l){
        return ValArray[n];
    }
    if(x<=l && r<=y){
        return ValArray[n];
    }
    long long val=GetValueRange(x,y,l,(l+r)/2,n*2)+GetValueRange(x,y,(l+r)/2+1,r,n*2+1);
    return val;
}

pair<int,int> GetBestRange(int x,int y,int l, int r,int n){
    if(x>r){
        return {INFint,0};
    }
    if(y<l){
        return {INFint,0};
    }
    if(x<=l && r<=y){
        return WeightsSegTree[n];
    }
    pair<int,int> val=min(GetBestRange(x,y,l,(l+r)/2,n*2),GetBestRange(x,y,(l+r)/2+1,r,n*2+1));
    return val;
}

long long getValue(int x){
    int pos=XtoIndx[x];
    return GetValueRange(pos,pos+RangeSize[x]-1,0,RangeSize.size(),1);
}

pair<int,int> getBest(int x){
    int pos=XtoIndx[x];
    return GetBestRange(pos,pos+RangeSize[x]-1,0,RangeSize.size(),1);
}

long long dfsGetVal(int x,int L,int R){
    long long baseCost=0;
    if(Children[x].size()==0){
        int cost=L*getBest(x).first;
        setWeightTree(XtoIndx[x],0,XtoIndx.size(),1,{INFint,0});
        
        
        SetValue(XtoIndx[x],0,XtoIndx.size(),1,L);
        return cost;
    }
    
    for(int i=0;i<Children[x].size();i++){
        baseCost+=dfsGetVal(Children[x][i],L,R);
    }
    int val=getValue(x);
    while(val>R){
        pair<int,int> P=getBest(x);
        long long sub=getValue(P.second);
        if(val-sub+L<R){
            SetValue(XtoIndx[P.second],0,XtoIndx.size(),1,sub-val+R);
            baseCost+=P.first*(val-R);
            val=R;
        }
        else{
            SetValue(XtoIndx[P.second],0,XtoIndx.size(),1,L);
            setWeightTree(XtoIndx[P.second],0,XtoIndx.size(),1,{INFint,0});
            val-=sub-L;
            baseCost+=P.first*(sub);
        }
    }
    return baseCost;
}

long long query(int L, int R){
    ValArray=vector<long long>(RangeSize.size()*4);
    vector<pair<int,int>> WtC=WeightsSegTree;
    return dfsGetVal(0,L,R);
    
}

• 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