제출 #648803

#제출 시각아이디문제언어결과실행 시간메모리
648803ymmRegions (IOI09_regions)C++17
35 / 100
8096 ms131072 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x) typedef long long ll; typedef std::pair<int, int> pii; typedef std::pair<ll , ll > pll; using namespace std; const int S = 128; const int N = 400'032 + S; const int R = 25'010; int reg[N]; int len = 0; int exp_reg[N]; int delta[N]; vector<int> bl_regs[N/S]; int cnt[N/S][S+1]; int scnt[N/S][S+1]; short sum[N/S][S+1][S+1]; vector<int> A[N]; int n, r, q; void dfs(int v) { exp_reg[len] = reg[v]; delta[len] = 1; ++len; for (int u : A[v]) dfs(u); exp_reg[len] = reg[v]; delta[len] = -1; ++len; } int compress(int i, int x) { auto it = lower_bound(bl_regs[i].begin(), bl_regs[i].end(), x); if (it == bl_regs[i].end() || *it != x) return S; return it - bl_regs[i].begin(); } void calc_block(int bl) { int l = bl*S, r = min(bl*S+S, len); int ans[S][S] = {}, pre[S] = {}; Loop (i,l,r) { int reg = exp_reg[i]; Loop (j,0,S) ans[reg][j] += pre[j]; pre[reg] += delta[i]; } Loop (i,0,S) Loop (j,0,S) sum[bl][i][j] = ans[j][i]; } void comp_block(int bl) { int l = bl*S, r = min(bl*S+S, len); static int arr[R]; Loop (i,l,r) bl_regs[bl].push_back(exp_reg[i]); sort(bl_regs[bl].begin(), bl_regs[bl].end()); bl_regs[bl].resize( unique(bl_regs[bl].begin(), bl_regs[bl].end()) - bl_regs[bl].begin()); Loop (i,0,bl_regs[bl].size()) arr[bl_regs[bl][i]] = i; Loop (i,l,r) exp_reg[i] = arr[exp_reg[i]]; } void init() { for (int l = 0; l < len; l += S) { int r = min(len, l + S); comp_block(l/S); calc_block(l/S); Loop (i,l,r) { cnt[l/S][exp_reg[i]]++; scnt[l/S][exp_reg[i]] += delta[i]; } } } int solve(int r1, int r2) { int ans = 0, pre = 0; Loop (i,0,(len+S-1)/S) { int cr1 = compress(i, r1); int cr2 = compress(i, r2); ans += pre * cnt[i][cr2]; ans += sum[i][cr1][cr2]; pre += scnt[i][cr1]; } return ans/2; } int main() { cin.tie(0) -> sync_with_stdio(false); cin >> n >> r >> q; cin >> reg[0]; Loop (i,1,n) { int p; cin >> p >> reg[i]; A[p-1].push_back(i); } dfs(0); init(); while (q--) { int r1, r2; cin >> r1 >> r2; cout << solve(r1, r2) << '\n'; cout.flush(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...