Submission #1004618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004618		Mardonbekhazratov	Regions (IOI09_regions)	C++17	35 / 100	8100 ms	60104 KiB

regions

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

struct mergeSortTree{
    int N,n;
    vector<vector<int>>tree;

    void build(int v,int l,int r,vector<int>&a){
        if(l>=n) return;
        if(r-l==1){
            tree[v]={a[l]};
            return;
        }

        int mid=(l+r)/2;
        build(v<<1,l,mid,a);
        build(v<<1|1,mid,r,a);
        merge(tree[v<<1].begin(),tree[v<<1].end(),tree[v<<1|1].begin(),tree[v<<1|1].end(),back_inserter(tree[v]));
    }

    mergeSortTree(vector<int>&a){
        n=(int)a.size();
        N=1;
        while(N<n) N<<=1;
        tree.resize(2*N);
        build(1,0,N,a);
    }

    // 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,int x){
        if(ql>=r || l>=qr) return 0;
        if(l>=ql && qr>=r) return lower_bound(tree[v].begin(),tree[v].end(),x+1)-lower_bound(tree[v].begin(),tree[v].end(),x);
        
        int mid=(l+r)/2;

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

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

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

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

signed main(){
    cin>>n>>r>>q;
    h.resize(n+1);
    a.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);
    }
    for(int i=1;i<=n;i++){
        a[h[i]].push_back(i);
    }
    tin.resize(n+1);
    tout.resize(n+1);
    dfs(1);
    mergeSortTree S(b);
    while(q--){
        int r1,r2;
        cin>>r1>>r2;
        int ans=0;
        for(int x:a[r1]){
            ans+=S.get(tin[x],tout[x],r2);
        }
        cout<<ans<<'\n';
    }
}

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