#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 = 400;
const int maxL = 1 + 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];
vpii inc_list[1+R];
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});
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]) cout << large_top[norm[r1]][r2] << '\n';
else if(norm[r2]) 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 |
21 ms |
34068 KB |
Output is correct |
2 |
Correct |
19 ms |
34024 KB |
Output is correct |
3 |
Correct |
21 ms |
34024 KB |
Output is correct |
4 |
Correct |
20 ms |
34120 KB |
Output is correct |
5 |
Correct |
27 ms |
34168 KB |
Output is correct |
6 |
Correct |
35 ms |
34236 KB |
Output is correct |
7 |
Correct |
59 ms |
34308 KB |
Output is correct |
8 |
Correct |
47 ms |
34436 KB |
Output is correct |
9 |
Correct |
46 ms |
34988 KB |
Output is correct |
10 |
Correct |
101 ms |
35672 KB |
Output is correct |
11 |
Correct |
83 ms |
36440 KB |
Output is correct |
12 |
Correct |
117 ms |
37328 KB |
Output is correct |
13 |
Correct |
189 ms |
37944 KB |
Output is correct |
14 |
Correct |
195 ms |
38992 KB |
Output is correct |
15 |
Correct |
223 ms |
41124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
860 ms |
45492 KB |
Output is correct |
2 |
Correct |
1006 ms |
46072 KB |
Output is correct |
3 |
Correct |
1678 ms |
47720 KB |
Output is correct |
4 |
Correct |
268 ms |
39108 KB |
Output is correct |
5 |
Correct |
447 ms |
40032 KB |
Output is correct |
6 |
Correct |
671 ms |
42296 KB |
Output is correct |
7 |
Correct |
1103 ms |
45580 KB |
Output is correct |
8 |
Runtime error |
75 ms |
76720 KB |
Execution killed with signal 11 |
9 |
Correct |
1364 ms |
59208 KB |
Output is correct |
10 |
Runtime error |
91 ms |
82680 KB |
Execution killed with signal 11 |
11 |
Correct |
2737 ms |
66608 KB |
Output is correct |
12 |
Correct |
1116 ms |
63912 KB |
Output is correct |
13 |
Correct |
1402 ms |
63724 KB |
Output is correct |
14 |
Correct |
1689 ms |
65864 KB |
Output is correct |
15 |
Correct |
2181 ms |
67024 KB |
Output is correct |
16 |
Correct |
1955 ms |
66804 KB |
Output is correct |
17 |
Correct |
1897 ms |
65896 KB |
Output is correct |