Submission #1259844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259844		torment	Regions (IOI09_regions)	C++20	100 / 100	3624 ms	29336 KiB

regions

#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 5;
const int R = 25005;
const int B = 450;
vector<int> g[N], reg[R];
int r12[B][R], r21[B][R], in[N], out[N], T = 0;
void dfs(int node, int par){
    in[node] = ++T;
    for(int &v : g[node]){
        if(v == par)continue;
        dfs(v, node);
    }
    out[node] = T;
}
struct BIT{
    vector<int>fen;
    int sz;
    BIT(int n){
        sz = n;
        fen.resize(n + 1);
    }
    void Update(int pos, int val){
        while(pos <= sz){
            fen[pos] += val;
            pos += (pos & -pos);
        }
    }
    int Sum(int pos){
        int s = 0;
        while(pos > 0){
            s += fen[pos];
            pos -= (pos & -pos);
        }
        return s;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    for(int i = 1;i <= n;++i){
        if(i != 1){
            int p;
            cin >> p;
            g[p].push_back(i);
            g[i].push_back(p);
        }
        int h;
        cin >> h;
        reg[h].push_back(i);
    }
    dfs(1, 1);
    vector<int>S, s(n + 1, -1);
    for(int i = 1;i <= r;++i){
        if(reg[i].size() > B){
            s[i] = S.size();
            S.push_back(i);
        }
    }
    for(int r1 = 0;r1 < (int)S.size();++r1){
        vector<int>v(n + 2);
        for(int j : reg[S[r1]]){
            v[in[j]]++;
            v[out[j] + 1]--;
        }
        for(int i = 1;i <= n;++i){
            v[i] += v[i - 1];
        }
        for(int r2 = 1;r2 <= r;++r2){
            for(int j : reg[r2]){
                r12[r1][r2] += v[in[j]];
            }
        }
    }
    for(int r2 = 0;r2 < (int)S.size();++r2){
        vector<int>v(n + 1);
        for(int j : reg[S[r2]]){
            v[in[j]]++;
        }
        for(int i = 1;i <= n;++i){
            v[i] += v[i - 1];
        }
        for(int r1 = 1;r1 <= r;++r1){
            for(int j : reg[r1]){
                r21[r2][r1] += v[out[j]] - v[in[j] - 1];
            }
        }
    }
    BIT tree(n);
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(s[r1] != -1){
            cout << r12[s[r1]][r2] << endl;
        }
        else if(s[r2] != -1){
            cout << r21[s[r2]][r1] << endl;
        }
        else{
            int res = 0;
            for(int j : reg[r2]){
                tree.Update(in[j], 1);
            }
            for(int j : reg[r1]){
                res += tree.Sum(out[j]) - tree.Sum(in[j] - 1);
            }
            for(int j : reg[r2]){
                tree.Update(in[j], -1);
            }
            cout << res << endl;
        }
    }
}

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