Submission #542592

#	Time	Username	Problem	Language	Result	Execution time	Memory
542592		Netr	Regions (IOI09_regions)	C++14	7 / 100	8080 ms	131072 KiB

regions

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif

#define lsb(x) (x&(-x))

const int MAXN = 2e5 + 5;
const int MAXR = 3e4 + 5;

int N, R, Q, regions[MAXN], tour[MAXN], tme[MAXN][2], timer = 1;
vector<int> adj[MAXN];
map<pi,int> queries;
map<int,int> tdft[MAXN], buft[MAXN];
vector<int> pbr[MAXR];

void updatetd(int p, int t, int v){
    for(; p <= N; p += lsb(p)){
        if(tdft[p].count(t)){
            tdft[p][t] += v;
        }else{
            tdft[p][t] = v;
        }
    }
}

int querytd(int p, int t){
    int res = 0;
    for(; p != 0; p -= lsb(p)){
        if(tdft[p].count(t)){
            res += tdft[p][t];
        }
    }
    return res;
}

int rangeQuerytd(int l, int r, int t){
    return querytd(r, t) - querytd(l-1, t);
}

void updatebu(int p, int t, int v){
    for(; p <= N; p += lsb(p)){
        if(buft[p].count(t)){
            buft[p][t] += v;
        }else{
            buft[p][t] = v;
        }
    }
}

void rangeUpdatebu(int l, int r, int t, int v){
    updatebu(l, t, v);
    updatebu(r+1, t, -v);
}

int querybu(int p, int t){
    int res = 0;
    for(; p != 0; p -= lsb(p)){
        if(buft[p].count(t)){
            res += buft[p][t];
        }
    }
    return res;
}

void dfs(int n, int p = 1){
    tour[timer] = n;
    tme[n][0] = timer++;

    for(int e : adj[n]){
        if(e == p) continue;
        dfs(e, n);
    }

    tme[n][1] = timer-1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> R >> Q >> regions[1];
    for(int i = 2; i <= N; i++){
        int sk, hk;
        cin >> sk >> hk;
        adj[sk].push_back(i);
        adj[i].push_back(sk);
        regions[i] = hk;
        pbr[hk].push_back(i);
    }

    dfs(1);
   
    for(int i = 1; i <= N; i++){
        updatetd(i, regions[tour[i]], 1);
        rangeUpdatebu(tme[i][0], tme[i][1], regions[i], 1);
    }

    D("Euler tour: ")
    for(int i = 1; i <= N; i++){
        D("%d ", tour[i]);
    }
    D("\ntd ft queries:\n");
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= R; j++){
            D("Person %d, region %d = %d\n", i, j, rangeQuerytd(tme[i][0], tme[i][1], j));
        }
    }
    D("\nbu ft queries:\n");
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= R; j++){
            D("Person %d, region %d = %d\n", i, j, querybu(tme[i][0], j));
        }
    }

    for(int z = 0; z < Q; z++){
        int r1, r2;
        cin >> r1 >> r2;
        if(queries.count({r1,r2})){
            cout << queries[{r1,r2}] << "\n";
            cout.flush();
            continue;
        }
        int ans = 0;
        if(r1 >= r2){
            // top down
            for(int i : pbr[r1]){
                ans += rangeQuerytd(tme[i][0], tme[i][1], r2); 
            }
        }else{
            // bottom up
            for(int i : pbr[r2]){
                ans += querybu(tme[i][0], r1);
            }
        }
        queries[{r1,r2}] = ans;
        cout << ans << "\n";
        cout.flush();
    }
}

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