Submission #1004602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004602		Mardonbekhazratov	Regions (IOI09_regions)	C++17	0 / 100	141 ms	131072 KiB

regions

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

struct SegTree{
    int N;
    vector<int>tree;

    void build(int n){
        N=1;
        while(N<n) N<<=1;

        tree.assign(2*N,0);
    }

    void update(int v,int l,int r,int id,int x){
        cout<<v;
        if(r-l==1){
            tree[v]+=x;
            return;
        }

        int mid=(l+r)/2;

        if(mid>id) update(v<<1,l,mid,id,x);
        else update(v<<1|1,mid,r,id,x);

        tree[v]=tree[v<<1]+tree[v<<1|1];
    }

    void update(int id,int x){
        return update(1,0,N,id,x);
    }

    int get(int v,int l,int r,int ql,int qr){
        if(ql>=r || l>=qr) return 0;
        if(l>=ql && qr>=r) return tree[v];
        
        int mid=(l+r)/2;

        return get(v<<1,l,mid,ql,qr)+get(v<<1|1,mid,r,ql,qr);
    }

    int get(int l,int r){
        return get(1,0,N,l,r);
    }
};

int n,r,q,timer = 0;
vector<int>h,tin,tout;
vector<vector<int>>v,a,dp;
vector<SegTree>S;

void dfs(int x){
    tin[x]=timer++;
    for(int z:v[x]){
        dfs(z);
    }
    tout[x]=timer;
}

int solve(int r1,int r2){
    if(dp[r1][r2]!=-1) return dp[r1][r2];
    int ans=0;
    for(int x:a[r1]){
        ans+=S[r2].get(tin[x],tout[x]);
    }
    return dp[r1][r2]=ans;
}

signed main(){
    cin>>n>>r>>q;
    h.resize(n+1);
    a.resize(r+1);
    S.resize(r+1);
    cin>>h[1];
    v.assign(n+1,vector<int>(0));
    dp.assign(r+1,vector<int>(r+1,-1));
    for(int i=2,x;i<=n;i++){
        cin>>x>>h[i];
        v[x].push_back(i);
    }
    tin.resize(n+1);
    tout.resize(n+1);
    dfs(1);
    for(int i=1;i<=n;i++){
        a[h[i]].push_back(i);
    }
    for(int i=1;i<=r;i++){
        S[i].build(timer);
        for(int x:a[i]){
            S[i].update(tin[x],1);
        }
    }
    while(q--){
        int r1,r2;
        cin>>r1>>r2;
        cout<<solve(r1,r2)<<'\n';
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85