Submission #1064675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064675		orcslop	Regions (IOI09_regions)	C++17	100 / 100	3432 ms	57092 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define int 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>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
 
const int MAXR = 25005; 
const int MAXN = 2e5 + 5; 
const int RT = 450; 

template <class T> class SGT {
  private:
    const T DEFAULT = 0;
    vector<T> tree;
    int n;

  public:
    SGT(int n) : n(n), tree(n * 2, DEFAULT) {}

    void update(int a, int b, T val) {
        a += n;
        tree[a] += val;
        for (a /= 2; a >= 1; a /= 2) {
            tree[a] = tree[2 * a] + tree[2 * a + 1]; 
        }
        b += n + 1; 
        tree[b] -= val; 
        for(b /= 2; b >= 1; b /= 2) {
            tree[b] = tree[2 * b] + tree[2 * b + 1]; 
        }
    }

    T query(int k) {
        int a = n, b = k + n; 
        T s = DEFAULT;
        while(a <= b){
            if (a % 2 == 1) s += tree[a++]; 
            if (b % 2 == 0) s += tree[b--]; 
            a /= 2; b /= 2; 
        }
        return s;
    }
};
 
int n, r, q, timer; 
int h[MAXN]; 
int tin[MAXN]; 
int subs[MAXN]; 
int pre[RT][MAXN]; 
SGT<int> tree(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; 
    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(auto x : occ[i]){
                tree.update(tin[x], tin[x] + subs[x] - 1, 1); 
            }
            for(int j = 1; j < MAXR; j++){
                for(auto x : eul[j]){
                    pre[curr][j] += tree.query(x); 
                }
            }
            for(auto x : occ[i]){
                tree.update(tin[x], tin[x] + subs[x] - 1, -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; 
}

Compilation message (stderr)

regions.cpp: In instantiation of 'SGT<T>::SGT(long long int) [with T = long long int]':
regions.cpp:57:19:   required from here
regions.cpp:22:9: warning: 'SGT<long long int>::n' will be initialized after [-Wreorder]
   22 |     int n;
      |         ^
regions.cpp:21:15: warning:   'std::vector<long long int, std::allocator<long long int> > SGT<long long int>::tree' [-Wreorder]
   21 |     vector<T> tree;
      |               ^~~~
regions.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     SGT(int n) : n(n), tree(n * 2, DEFAULT) {}
      |     ^~~

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