oj.uz

Submission #1064675

# Submission time Handle Problem Language Result Execution time Memory
1064675 2024-08-18T16:41:56 Z orcslop Regions (IOI09_regions) C++17
100 / 100
 3432 ms 57092 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 3 ms 13912 KB Output is correct
3 Correct 4 ms 13912 KB Output is correct
4 Correct 4 ms 13912 KB Output is correct
5 Correct 6 ms 14048 KB Output is correct
6 Correct 8 ms 13912 KB Output is correct
7 Correct 19 ms 13912 KB Output is correct
8 Correct 25 ms 13912 KB Output is correct
9 Correct 28 ms 14424 KB Output is correct
10 Correct 62 ms 14424 KB Output is correct
11 Correct 80 ms 14836 KB Output is correct
12 Correct 96 ms 15192 KB Output is correct
13 Correct 125 ms 15448 KB Output is correct
14 Correct 166 ms 15700 KB Output is correct
15 Correct 183 ms 17436 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 40976 KB Output is correct
2 Correct 1648 ms 37060 KB Output is correct
3 Correct 2197 ms 33936 KB Output is correct
4 Correct 181 ms 15704 KB Output is correct
5 Correct 244 ms 16728 KB Output is correct
6 Correct 665 ms 44228 KB Output is correct
7 Correct 1160 ms 38732 KB Output is correct
8 Correct 1619 ms 51276 KB Output is correct
9 Correct 1592 ms 23888 KB Output is correct
10 Correct 3432 ms 57092 KB Output is correct
11 Correct 2555 ms 27124 KB Output is correct
12 Correct 997 ms 27216 KB Output is correct
13 Correct 1409 ms 27656 KB Output is correct
14 Correct 1985 ms 48228 KB Output is correct
15 Correct 2380 ms 29796 KB Output is correct
16 Correct 2392 ms 32860 KB Output is correct
17 Correct 2600 ms 52608 KB Output is correct