Submission #914648

#	Time	Username	Problem	Language	Result	Execution time	Memory
914648		anarch_y	Regions (IOI09_regions)	C++17	35 / 100	8102 ms	68356 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
 
const int MX = 25001;
 
struct node{
    int val;
    int l, r;
};
 
struct pseg{
    static const int LIM = 4000000;
    node d[LIM];
    int nex = 0;
    vector<int> loc;
 
    int copy(int cur){
        int x = nex++;
        d[x] = d[cur];
        return x;
    }
 
    void push(int x){
        d[x].val = d[d[x].l].val + d[d[x].r].val;
    }
 
    int build(vector<int> &A, int L, int R){
        int cur = nex++;
        if(L == R){
            if(L < sz(A)) d[cur].val = A[L];
            return cur;
        }
        int M = (L+R)/2;
        d[cur].l = build(A, L, M);
        d[cur].r = build(A, M+1, R);
        push(cur);
        return cur;
    }
 
    void build(vector<int> &A){
        loc[0] = build(A, 0, MX-1);
    }
 
    int upd(int cur, int pos, int v, int L, int R){
        if(R < pos or pos < L) return cur;
        int x = copy(cur);
        if(pos <= L and R <= pos){
            d[x].val += v;
            return x;
        }
        int M = (L+R)/2;
        d[x].l = upd(d[x].l, pos, v, L, M);
        d[x].r = upd(d[x].r, pos, v, M+1, R);
        push(x);
        return x;
    }
 
    int upd(int cur, int id, int v){
        return upd(cur, id, v, 0, MX-1);
    }
 
    int query(int cur, int a, int b, int L, int R){  
        if(R < a or b < L) return 0;
        if(a <= L and R <= b) return d[cur].val;
        int M = (L+R)/2;
        int s1 = query(d[cur].l, a, b, L, M);
        int s2 = query(d[cur].r, a, b, M+1, R);
        return s1+s2;
    }
 
    int query(int cur, int a, int b){
        return query(cur, a, b, 0, MX-1);
    }
};
 
pseg P;
 
int query(int x, int y, int c){
    if(x == 0) return P.query(P.loc[y], c, c);
    return P.query(P.loc[y], c, c) - P.query(P.loc[x-1], c, c);
}
 
const int maxn = 200001;
vector<int> adj[maxn];
int sub[maxn], id[maxn], home[maxn];
vector<int> tour;
 
void dfs(int s, int p){
    sub[s] = 1;
    tour.pb(s);
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        sub[s] += sub[u];
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int N, R, Q; cin >> N >> R >> Q;
    vector<int> reg[R+1];
    int h; cin >> h;
    reg[h].pb(1); home[1] = h;
    for(int i=2; i<=N; i++){
        int p, r; cin >> p >> r;
        adj[i].pb(p); adj[p].pb(i);
        reg[r].pb(i);
        home[i] = r;
    }
    dfs(1, 0);
 
    vector<int> A(N, 0);
    for(int i=0; i<N; i++){
        id[tour[i]] = i;
        A[i] = home[tour[i]];
    }
 
    P.loc.resize(maxn);
    vector<int> t(MX, 0);
    t[A[0]] = 1;
    P.build(t);
    for(int i=1; i<N; i++){
        P.loc[i] = P.upd(P.loc[i-1], A[i], 1);
    }
 
    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        int ans = 0;
        for(auto a: reg[r1]){
            ans += query(id[a], id[a]+sub[a]-1, r2);
        }
        cout << ans << "\n";
        cout.flush();
    }
}

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