Submission #1091302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091302		asli_bg	Regions (IOI09_regions)	C++11	30 / 100	8098 ms	105692 KiB

regions

#pragma GCC optimize ("O3,unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef priority_queue<int> pq;
 
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
 
#define carp(x,y,mod) (((x)%mod)*((y)%mod))%mod
#define topla(x,y,mod) (((x)%mod)+((y)%mod))%mod
 
#define mid (l+r)/2
//#define endl '\n'
 
const int MAXN=2e5+5;
const int MAXK=30;

int n,q,r;
vi adj[MAXN];
vi euler;
int sub[MAXN],ind[MAXN],dep[MAXN];
int p[MAXN];
vi t[4*MAXN];
vi reg[MAXN];
int home[MAXN];

void dfs(int nd,int ata,int h){
    dep[nd]=h;
    sub[nd]=1;
    euler.pb(nd);
    for(auto kom:adj[nd]){
        if(kom!=ata){
            dfs(kom,nd,h+1);
            sub[nd]+=sub[kom];
        }
    }
}

vi merge(vi& a,vi& b){
    vi c;
    int sz1=a.size();
    int sz2=b.size();
    int p1,p2;
    p1=p2=0;
    while(p1<sz1 or p2<sz2){
        if(p2>=sz2 or (p1<sz1 and a[p1]<=b[p2])){
            c.pb(a[p1++]);
        }
        else c.pb(b[p2++]);
    }
    return c;
}

void build(int nd=1,int l=1,int r=n){
    if(l==r){
        t[nd].pb(home[euler[l]]);
        return;
    }
    build(nd*2,l,mid);
    build(nd*2+1,mid+1,r);
    t[nd]=merge(t[nd*2],t[nd*2+1]);
}

int query(int ql,int qr,int vv,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return 0;
    if(ql<=l and r<=qr){
        auto bir=lower_bound(all(t[nd]),vv);
        auto iki=upper_bound(all(t[nd]),vv);
        return iki-bir;
    }
    auto s1=query(ql,qr,vv,nd*2,l,mid);
    auto s2=query(ql,qr,vv,nd*2+1,mid+1,r);
    return s1+s2;
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    euler.pb(0);
    cin>>n>>r>>q;
    cin>>home[1];
    reg[home[1]].pb(1);
    FORE(i,2,n+1){
        cin>>p[i]>>home[i];
        reg[home[i]].pb(i);
        adj[p[i]].pb(i);
        adj[i].pb(p[i]);
    }

    dfs(1,0,0);
    FORE(i,1,n+1){
        ind[euler[i]]=i;
    }
    build();

    while(q--){
        int a,b;
        cin>>a>>b;
        int cev=0;
        for(auto el:reg[a]){
            cev+=query(ind[el],ind[el]+sub[el]-1,b);
        }
        cout<<cev<<endl;
    }
}

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