// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define f first
#define s second
#define pb push_back
#define inf ~((long long)1<<63)
using namespace std;
const int mod = 1000000007;
void setio(string name = "") {
ios::sync_with_stdio(false), cin.tie(nullptr);
if(name.length()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void add(vector<int>& bit, int ind, int val){for(ind++; ind < bit.size(); ind += ind & -ind) { bit[ind] += val; };}
int prev(vector<int>& bit, int ind) {
int total = 0;
for (ind++; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
return total;
}
int sum(vector<int>& bit, int a, int b){
return prev(bit, b)-(a == 0 ? 0:prev(bit, a-1));
}
int N, R, timer = 0;
vector<vector<int>> cnt;
vector<int> big;
vector<int> st, en;
vector<vector<int>> g;
vector<vector<int>> ans;
vector<int> nums;
vector<vector<int>> sums;
void dfs(int s, vector<int>& curr){
if(big[nums[s]]+1) curr[big[nums[s]]]++;
else for(int i = 0; i<curr.size(); i++) ans[s][i] = curr[i];
st[s] = timer++;
for(int i: g[s]) dfs(i, curr);
if(big[nums[s]]+1) curr[big[nums[s]]]--;
en[s] = timer-1;
}
int main() {
setio();
int Q; cin >> N >> R >> Q;
g.resize(N, vector<int>(0));
nums.resize(N);
cin >> nums[0];
for(int i = 1; i<N; i++){
int par; cin >> par;
g[par-1].pb(i);
cin >> nums[i];
}
cnt.resize(R, vector<int>(0));
for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
int block = sqrt(N);
if(N > 1000) block = 1000;
big.resize(R, -1);
int p = 0;
for(int i = 0; i<R; i++) if(cnt[i].size() >= block) big[i] = p++;
st.resize(N);
en.resize(N);
ans.resize(N, vector<int>(p));
vector<int> curr(p);
dfs(0, curr);
sums.resize(p, vector<int>(N+1));
for(int i = 0; i<N; i++) if(big[nums[i]]+1) add(sums[big[nums[i]]], st[i], 1);
vector<int> b(N+1);
map<int, int> mem;
while(Q--> 0){
int up, down; cin >> up >> down; --up, --down;
if(mem.find(up*R+down) != mem.end()) cout << mem[up*R+down] << endl;
else if(big[down]+1){
int ret = 0;
for(int i: cnt[up]) ret+=sum(sums[big[down]], st[i], en[i]);
mem[up*R+down] = ret;
cout << ret << endl;
}else if(big[up]+1){
int ret = 0;
for(int i: cnt[down])
ret+=ans[i][big[up]];
mem[up*R+down] = ret;
cout << ret << endl;
}else{
int ret = 0;
for(int i: cnt[down]) add(b, st[i], 1);
for(int i: cnt[up]) ret+=sum(b, st[i], en[i])-(up == down ? 1:0);
for(int i: cnt[down]) add(b, st[i], -1);
mem[up*R+down] = ret;
cout << ret << endl;
}
}
}
Compilation message
regions.cpp: In function 'void add(std::vector<int>&, int, int)':
regions.cpp:19:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | void add(vector<int>& bit, int ind, int val){for(ind++; ind < bit.size(); ind += ind & -ind) { bit[ind] += val; };}
| ~~~~^~~~~~~~~~~~
regions.cpp: In function 'void dfs(int, std::vector<int>&)':
regions.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | else for(int i = 0; i<curr.size(); i++) ans[s][i] = curr[i];
| ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:61:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | for(int i = 0; i<R; i++) if(cnt[i].size() >= block) big[i] = p++;
| ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp: In function 'void setio(std::string)':
regions.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
2 ms |
208 KB |
Output is correct |
| 4 |
Correct |
5 ms |
328 KB |
Output is correct |
| 5 |
Correct |
7 ms |
336 KB |
Output is correct |
| 6 |
Correct |
16 ms |
460 KB |
Output is correct |
| 7 |
Correct |
23 ms |
464 KB |
Output is correct |
| 8 |
Correct |
33 ms |
604 KB |
Output is correct |
| 9 |
Correct |
48 ms |
1204 KB |
Output is correct |
| 10 |
Correct |
92 ms |
1652 KB |
Output is correct |
| 11 |
Correct |
103 ms |
2252 KB |
Output is correct |
| 12 |
Correct |
165 ms |
3152 KB |
Output is correct |
| 13 |
Correct |
220 ms |
2932 KB |
Output is correct |
| 14 |
Correct |
296 ms |
3884 KB |
Output is correct |
| 15 |
Correct |
403 ms |
6952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1192 ms |
12872 KB |
Output is correct |
| 2 |
Correct |
1587 ms |
15160 KB |
Output is correct |
| 3 |
Correct |
2457 ms |
21636 KB |
Output is correct |
| 4 |
Correct |
391 ms |
4604 KB |
Output is correct |
| 5 |
Correct |
428 ms |
7032 KB |
Output is correct |
| 6 |
Correct |
776 ms |
7216 KB |
Output is correct |
| 7 |
Correct |
670 ms |
8496 KB |
Output is correct |
| 8 |
Correct |
2066 ms |
17004 KB |
Output is correct |
| 9 |
Correct |
3581 ms |
22796 KB |
Output is correct |
| 10 |
Correct |
5997 ms |
30100 KB |
Output is correct |
| 11 |
Correct |
5593 ms |
27780 KB |
Output is correct |
| 12 |
Correct |
1646 ms |
31356 KB |
Output is correct |
| 13 |
Correct |
2182 ms |
32916 KB |
Output is correct |
| 14 |
Correct |
3103 ms |
49404 KB |
Output is correct |
| 15 |
Correct |
4467 ms |
40896 KB |
Output is correct |
| 16 |
Correct |
4340 ms |
47128 KB |
Output is correct |
| 17 |
Correct |
4253 ms |
61140 KB |
Output is correct |
