Submission #1064653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064653		orcslop	Regions (IOI09_regions)	C++17	40 / 100	8058 ms	35664 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>
 
const int MAXR = 25005; 
const int MAXN = 2e5 + 5; 
const int RT = 450; 

template <class T> class BIT {
  private:
    int n;
    vector<T> bit;
    vector<T> arr;

  public:
    BIT(int n) : n(n), bit(n + 1), arr(n) {}

    void set(int k, T val) { add(k, val - arr[k]); }

    void add(int k, T val) {
        arr[k] += val;
        k++;
        for (; k <= n; k += k & -k) { bit[k] += val; }
    }

    T query(int a, int b) {
        b++;
        T s = 0;
        for (; a > 0; a -= a & -a) { s -= bit[a]; }
        for (; b > 0; b -= b & -b) { s += bit[b]; }
        return s;
    }
};
 
int n, r, q, timer; 
int h[MAXN]; 
int tin[MAXN]; 
int subs[MAXN]; 
int pre[RT][MAXN]; 
BIT<int> bit(MAXN); 
map<int, int> mp; 
vector<int> adj[MAXN]; 
vector<int> eul[MAXR], occ[MAXR]; 
 
void dfs(int node, int prev){
    subs[node] = 1; 
    tin[node] = timer++; 
    for(auto x : adj[node]){
        if(x == prev) continue; 
        dfs(x, node); 
        subs[node] += subs[x]; 
    }
}
 
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> r >> q; 
    // int RT = sqrt(n); 
    cin >> h[0]; 
    occ[h[0]].pb(0); 
    for(int i = 1; i < n; i++){
        int x; 
        cin >> x >> h[i]; 
        adj[--x].pb(i); 
        adj[i].pb(x); 
        occ[h[i]].pb(i); 
    }
    dfs(0, -1); 
    // for(int i = 0; i < n; i++){
    //     cout << tin[i] << ' '; 
    // }
    // cout << '\n'; 
    for(int i = 1; i < MAXR; i++){
        for(auto x : occ[i]) eul[i].pb(tin[x]); 
        sort(all(eul[i])); 
        sort(all(occ[i]), [](int &a, int &b){
            return tin[a] < tin[b]; 
        }); 
    }
    for(int i = 1; i < MAXR; i++){
        if(occ[i].size() >= RT) {
            int curr = mp[i] = mp.size(); 
            for(int j = 1; j < MAXR; j++){
                for(auto x : eul[j]) {
                    bit.add(x, 1); 
                }
                // for(int i = 0; i < n; i++){
                //     cout << bit.query(k, k) << ' '; 
                // }
                // cout << '\n'; 
                for(auto x : occ[i]){
                    pre[curr][j] += bit.query(tin[x], tin[x] + subs[x] - 1); 
                }
                for(auto x : eul[j]){
                    bit.add(x, -1); 
                }
            }
        }
    }
    for(int i = 0; i < q; i++){
        int a, b; 
        cin >> a >> b; 
        if(occ[a].size() >= RT) cout << pre[mp[a]][b] << endl; 
        else{
            int ans = 0; 
            for(auto x : occ[a]){
                auto lb = lower_bound(all(eul[b]), tin[x]); 
                auto ub = upper_bound(all(eul[b]), tin[x] + subs[x] - 1); 
                ans += ub - lb; 
            }
            cout << ans << endl; 
        }
    }
    return 0; 
}

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