Submission #1184201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184201		GGOSHAB	Regions (IOI09_regions)	C++20	70 / 100	8093 ms	166288 KiB

regions

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef ONPC
    #pragma GCC target("avx")
    #pragma GCC target("popcnt")

    #define cerr if (false) cerr
#endif

using namespace std;

#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;

mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
    return uniform_int_distribution<ll>(l, r)(gen64);
}

template<class T>
bool umin(T &a, const T &b) {
    return (a > b ? a = b, true : false);
}

template<class T>
bool umax(T &a, const T &b) {
    return (a < b ? a = b, true : false);
}

const int mod = 1e9 + 7;
ll mult(ll a, ll b) {
    return (a * b) % mod;
}

template<class T>
void add(T &a, const T &b) {
    a = (a + b) % mod;
}

const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;

const int maxn = 2e5 + 5, maxr = 25000 + 5;
constexpr int W = 100;

ll prc[maxn / W + 10][maxr];

using state = map<int, ll>;
void merge(state &a, state &b) {
    if (a.size() < b.size()) {
        swap(a, b);
    }
    for (auto [c, f] : b) {
        a[c] += f;
    }
}

vector<int> g[maxn];
int c[maxn], f[maxr];

int idx[maxr], tin[maxn], tout[maxn], timer = -1;
state dfs(int v = 1, int p = -1) {
    tin[v] = ++timer;
    state cur;
    for (int u : g[v]) {
        if (u != p) {
            state t = dfs(u, v);
            merge(cur, t);
        }
    }

    if (f[c[v]] > W) {
        for (auto [cu, f] : cur) {
            prc[idx[c[v]]][cu] += f;
        }
    }

    tout[v] = timer;
    cur[c[v]]++;
    return cur;
}

// void dfs(int v = 1, int p = -1) {
//     tin[v] = ++timer;
//     state cur;
//     for (int u : g[v]) {
//         if (u != p) {
//             dfs(u, v);
//         }
//     }

//     tout[v] = timer;
// }


struct segment_tree {
    int n;
    vector<vector<int>> t;
    segment_tree(int n) : n(n), t(2 * n + 10) {
        build(n);
    }
    void build(int _n) {
        n = _n;
        t.resize(2 * n + 10);
        vector<int> euler(n);
        for (int v = 1; v <= n; ++v) {
            euler[tin[v]] = c[v];
        }
        for (int i = 0; i < n; ++i) {
            t[i + n] = {euler[i]};
        }
        for (int v = n - 1; v > 0; --v) {
            merge(all(t[v << 1]), all(t[v << 1 | 1]), back_inserter(t[v]));
        }
    }
    ll get(int l, int r, int x) {
        r++;
        l = max(l, 0), r = min(r, n);
        l += n, r += n;
        ll res = 0;
        while (l < r) {
            if (l & 1) {
                res += upper_bound(all(t[l]), x) - lower_bound(all(t[l]), x);
                l++;
            }
            if (r & 1) {
                --r;
                res += upper_bound(all(t[r]), x) - lower_bound(all(t[r]), x);
            }
            l >>= 1, r >>= 1;
        }

        return res;
    }
};

void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    vector<vector<int>> a(r + 1);
    for (int v = 1; v <= n; ++v) {
        if (v != 1) {
            int p;
            cin >> p;
            g[p].push_back(v);
        }
        cin >> c[v];
        f[c[v]]++;
        a[c[v]].push_back(v);
    }

    int cur = 0;
    for (int x = 1; x <= r; ++x) {
        if (f[x] > W) {
            idx[x] = cur++;
            // for (int v : a[x]) {
            //     for (int c = 1; c <= r; ++c) {
            //         prc[idx[x]][c] += st.get(tin[v] + 1, tout[v], c);
            // }
        }
    }
    dfs();
    segment_tree st(n);

    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        if (f[r1] > W) {
            cout << prc[idx[r1]][r2] << endl;
        } else {
            ll ans = 0;
            for (int v : a[r1]) {
                ans += st.get(tin[v] + 1, tout[v], r2);
            }
            cout << ans << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

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