#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
const int maxN = 200'000;
const int maxR = 25'000;
// const int maxR = 500;
const int mns = 500;
const int maxL = 10 + (maxR/mns);
int N, R, Q;
vi H(1+maxN);
vi S(1+maxN);
vi children[1+maxN];
vi region_list[1+maxR];
vi norm(1+maxR, 0);
int large_ct = 0;
vvl large_bottom(1+maxL, vl(1 + maxR));
vvl large_top(1+maxL, vl(1 + maxR));
vi inc(1+maxL, 0);
vi dfs_order(1, 0);
vi order_index(1+maxN);
int dfs_ct = 0;
vi subtree(1+maxN, 1);
void dfs(int u)
{
dfs_order.push_back(u);
order_index[u] = ++dfs_ct;
for(int l = 1; l <= large_ct; l++)
large_top[l][H[u]] += inc[l];
if(norm[H[u]])
inc[norm[H[u]]]++;
for(int v: children[u])
{
dfs(v);
subtree[u] += subtree[v];
}
if(norm[H[u]])
inc[norm[H[u]]]--;
}
int main()
{
// cout << "done\n";
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> R >> Q;
cin >> H[1];
S[1] = 0;
for(int i = 2; i <= N; i++)
{
cin >> S[i] >> H[i];
children[S[i]].push_back(i);
}
for(int i = 1; i <= N; i++)
{
region_list[ H[i] ].push_back(i);
}
for(int r = 1; r <= R; r++)
{
if(sz(region_list[r]) >= mns)
{
norm[r] = ++large_ct;
}
}
dfs(1);
vi pos_list[1+N], neg_list[1+N];
for(int u = 1; u <= N; u++)
{
neg_list[order_index[u] - 1].push_back(H[u]);
pos_list[order_index[u] + subtree[u] - 1].push_back(H[u]);
}
// for(int u: dfs_order) cerr << u << ' ';
// cerr << '\n';
// for(int r = 1; r <= R; r++)
// {
// cerr << "r = " << r << " : ";
// for(int i = 1; i <= N)
// }
inc = vi(1+large_ct, 0);
for(int i = 0; i <= N; i++)
{
if(norm[H[dfs_order[i]]])
inc[ norm[H[dfs_order[i]]] ]++;
for(int j: neg_list[i])
for(int l = 1; l <= large_ct; l++)
large_bottom[l][j] -= inc[l];
for(int j: pos_list[i])
for(int l = 1; l <= large_ct; l++)
large_bottom[l][j] += inc[l];
// cerr << "i = " << i << ": " << dfs_order[i] << " \n";
// for(int r = 1; r <= R; r++) cerr << inc[r] << ' ';
// cerr << '\n';
}
vi point_list[1+R+1];
vpii inc_list[1+R+1];
for(int i = 1; i <= N; i++)
{
point_list[H[i]].push_back(order_index[i]);
inc_list[H[i]].push_back({order_index[i] + 1, +1});
inc_list[H[i]].push_back({order_index[i] + subtree[i], -1});
}
for(int r = 1; r <= R; r++)
{
sort(point_list[r].begin(), point_list[r].end());
sort(inc_list[r].begin(), inc_list[r].end());
}
for(int q = 1; q <= Q; q++)
{
int r1, r2;
cin >> r1 >> r2;
if(norm[r1])
{
// cerr << "case 1\n";
cout << large_top[norm[r1]][r2] << '\n';
}
else if(norm[r2])
{
// cerr << "case 2\n";
cout << large_bottom[norm[r2]][r1] << '\n';
}
else
{
ll res = 0;
ll curr = 0;
int ii = -1;
for(int p: point_list[r2])
{
while(ii+1 < sz(inc_list[r1]) && inc_list[r1][ii+1].first <= p)
{
ii++;
curr += inc_list[r1][ii].second;
}
res += curr;
}
cout << res << '\n';
}
cout.flush();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
32856 KB |
Output is correct |
2 |
Correct |
14 ms |
32904 KB |
Output is correct |
3 |
Correct |
15 ms |
32924 KB |
Output is correct |
4 |
Correct |
18 ms |
32900 KB |
Output is correct |
5 |
Correct |
21 ms |
32940 KB |
Output is correct |
6 |
Correct |
46 ms |
33048 KB |
Output is correct |
7 |
Correct |
31 ms |
33156 KB |
Output is correct |
8 |
Correct |
30 ms |
33244 KB |
Output is correct |
9 |
Correct |
66 ms |
33712 KB |
Output is correct |
10 |
Correct |
67 ms |
34512 KB |
Output is correct |
11 |
Correct |
132 ms |
35260 KB |
Output is correct |
12 |
Correct |
144 ms |
36104 KB |
Output is correct |
13 |
Correct |
175 ms |
36764 KB |
Output is correct |
14 |
Correct |
178 ms |
37812 KB |
Output is correct |
15 |
Correct |
183 ms |
39952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
556 ms |
44300 KB |
Output is correct |
2 |
Correct |
854 ms |
44876 KB |
Output is correct |
3 |
Correct |
1478 ms |
46472 KB |
Output is correct |
4 |
Correct |
225 ms |
37916 KB |
Output is correct |
5 |
Correct |
230 ms |
38840 KB |
Output is correct |
6 |
Correct |
657 ms |
41132 KB |
Output is correct |
7 |
Correct |
959 ms |
44400 KB |
Output is correct |
8 |
Correct |
825 ms |
48664 KB |
Output is correct |
9 |
Correct |
1063 ms |
58100 KB |
Output is correct |
10 |
Correct |
2039 ms |
60900 KB |
Output is correct |
11 |
Correct |
2459 ms |
65420 KB |
Output is correct |
12 |
Correct |
1161 ms |
62756 KB |
Output is correct |
13 |
Correct |
1616 ms |
62548 KB |
Output is correct |
14 |
Correct |
2106 ms |
64684 KB |
Output is correct |
15 |
Correct |
2736 ms |
65848 KB |
Output is correct |
16 |
Correct |
2246 ms |
65636 KB |
Output is correct |
17 |
Correct |
1857 ms |
64688 KB |
Output is correct |