Submission #1184204

#TimeUsernameProblemLanguageResultExecution timeMemory
1184204GGOSHABRegions (IOI09_regions)C++20
65 / 100
8096 ms78444 KiB
#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 = 1000; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...