# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
67425 | 2018-08-14T09:13:47 Z | Crown | Regions (IOI09_regions) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; #define lim 316 const int maxn = 2e5+5; const int maxr = 3e4+5; vector<int> adj[maxn]; int re[maxn]; int num[maxn]; int cnt[maxn]; int cur = 0; int n, r, q; vector<int> regions[maxn]; vector<int> blocks[maxn]; vector< ii > res[maxn]; void dfs(int u, int p) { cur++; num[u] = cur; cnt[u] = 1; for(auto v : adj[u]) { if(v == p) continue; dfs(v, u); cnt[u] += cnt[v]; } } bool cmp(int a, int b) { if(abs(a) != abs(b)) return abs(a)< abs(b); return a< b; } map<ii, ll> cache; int main() { scanf("%d %d %d", &n, &r, &q); scanf("%d", re+1); for(int i = 2; i<= n; i++) { int x; scanf("%d %d", &x, &re[i]); adj[x].pb(i); } dfs(1, 0); for(int i = 1; i<= n; i++) { regions[re[i]].pb(num[i]); blocks[re[i]].pb(num[i]); blocks[re[i]].pb(-num[i]-cnt[i]); } for(int i = 1; i<= r; i++) { sort(regions[i].begin(), regions[i].end()); sort(blocks[i].begin(), blocks[i].end(), cmp); vector< ii > tmp; for(int j = 0; j< (int) blocks[i].size(); j++) { if(tmp.empty() || abs(blocks[i][j]) != tmp.back().X) { tmp.pb(ii(abs(blocks[i][j]), blocks[i][j]>0?1:-1)); } else { tmp.back().Y += (blocks[i][j]>0?1:-1); } } if(!tmp.empty()) res[i].pb(tmp[0]); for(int j = 1; j< (int) tmp.size(); j++) { res[i].pb(ii(tmp[j].X, res[i].back().Y+tmp[j].Y)); } } while(q--) { int r1, r2; scanf("%d %d", &r1, &r2); if(cache.find(ii(r1, r2)) != cache.end()) { printf("%lld\n", cache[ii(r1, r2)]); fflush(stdout); continue; } if(r1.empty() || r2.empty()) { printf("0\n"); fflush(stdout); cache[ii(r1, r2)] = 0; } ll ret = 0; if(r1>= lim || r2>= lim) { if(r1> r2) { for(auto x : regions[r2]) { int ind = upper_bound(res[r1].begin(), res[r1].end(), ii(x, 1e9))-res[r1].begin()-1; if(ind< 0) continue; ret += res[r1][ind].Y; } } else { for(int i = 1; i< (int) res[r1].size(); i++) { int lb = res[r1][i-1].X; int rb = res[r1][i].X-1; int cnt = res[r1][i-1].Y; int cnt2 = lower_bound(regions[r2].begin(), regions[r2].end(), rb)-lower_bound(regions[r2].begin(), regions[r2].end(), lb-1); ret += 1LL*cnt*cnt2; } } } else { int pt = 0; for(auto x : regions[r2]) { while(pt< (int) res[r1].size() && res[r1][pt].X<= x) pt++; if(pt) ret += res[r1][pt-1].Y; } } cache[ii(r1, r2)] = ret; printf("%lld\n", ret); fflush(stdout); } }