#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 2e5,mxR = 2.5e4, oo = 1e9;
const int c = 448;
int h[mxN], in[mxN], out[mxN], hh[mxN];
vi kids[mxN];
vi sorted[mxR];
struct event {
int i; bool pos;
bool operator<(const event& o) const {
return i< o.i;
}
};
vector<event> events[mxR];
int cnt = 0;
void dfs(int at) {
hh[cnt] = h[at];
events[h[at]].push_back({cnt,true});
sorted[h[at]].push_back(cnt);
in[at] = cnt++;
for(int to: kids[at]) {
dfs(to);
}
out[at] = cnt;
events[h[at]].push_back({cnt,false});
}
int main() {
int n,r,q;
cin >> n >> r >> q;
for(int i=0;i<n;++i) {
if(i) {
int par;
cin >> par;
par--;
kids[par].push_back(i);
}
cin >> h[i];
h[i]--;
}
dfs(0);
for(int i=0;i<r;++i) {
sort(all(events[i]));
}
struct lookuptable {
vector<ll> ans,ans2;
int big;
lookuptable(int b, int rr) {
ans.resize(rr);
ans2.resize(rr);
big = b;
}
};
vector<lookuptable> lookup;
for(int b=0;b<r;++b) {
if((int)sorted[b].size()>=c) {
// precompute answer for all queries of form (i,e_2) or (e_1, i)
lookuptable l(b,r);
int overlap = 0;
auto& mevents = events[b];
// big group is above other group
for(int i=0,j=0;i<n;++i) {
while(j<mevents.size() and mevents[j].i<=i) {
if(mevents[j++].pos) {
overlap++;
} else {
overlap--;
}
}
l.ans[hh[i]]+=overlap;
}
// big group is under other group
// prefix sums?
vi pref(n+1,0);
for(int i=1;i<=n;++i) {
pref[i]+=pref[i-1]+(hh[i-1]==b);
}
for(int i=0;i<n;++i) {
l.ans2[h[i]]+=pref[out[i]] - pref[in[i]];
}
lookup.push_back(l);
}
}
while(q--) {
int a,b; cin >> a >> b; --a,--b;
if(sorted[a].size()>=c) {
int l=0,r = lookup.size()-1;
while(l<r) {
int mid = (l+r)/2;
if(lookup[mid].big < a) {
l=mid+1;
} else r = mid;
}
cout << lookup[l].ans[b] << endl;
} else if(sorted[b].size()>=c) {
int l=0,r = lookup.size()-1;
while(l<r) {
int mid = (l+r)/2;
if(lookup[mid].big < b) {
l=mid+1;
} else r = mid;
}
cout << lookup[l].ans2[a] << endl;
} else {
auto& es = events[a];
auto& v = sorted[b];
ll ans = 0;
int overlap = 0;
for(int i=0,j=0; i < v.size();++i) {
while(j<es.size() and es[j].i<=v[i]) {
if(es[j++].pos) {
overlap++;
} else {
overlap--;
}
}
ans+=overlap;
}
cout << ans << endl;
}
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | while(j<mevents.size() and mevents[j].i<=i) {
| ~^~~~~~~~~~~~~~~
regions.cpp:120:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0,j=0; i < v.size();++i) {
| ~~^~~~~~~~~~
regions.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while(j<es.size() and es[j].i<=v[i]) {
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6252 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6252 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6252 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6252 KB |
Output is correct |
| 5 |
Correct |
12 ms |
6252 KB |
Output is correct |
| 6 |
Correct |
25 ms |
6380 KB |
Output is correct |
| 7 |
Correct |
31 ms |
6380 KB |
Output is correct |
| 8 |
Correct |
37 ms |
6380 KB |
Output is correct |
| 9 |
Correct |
48 ms |
7020 KB |
Output is correct |
| 10 |
Correct |
78 ms |
7020 KB |
Output is correct |
| 11 |
Correct |
102 ms |
7424 KB |
Output is correct |
| 12 |
Correct |
153 ms |
8300 KB |
Output is correct |
| 13 |
Correct |
121 ms |
7916 KB |
Output is correct |
| 14 |
Correct |
192 ms |
8832 KB |
Output is correct |
| 15 |
Correct |
230 ms |
12620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
826 ms |
13208 KB |
Output is correct |
| 2 |
Correct |
1103 ms |
11780 KB |
Output is correct |
| 3 |
Correct |
1704 ms |
15920 KB |
Output is correct |
| 4 |
Correct |
279 ms |
8556 KB |
Output is correct |
| 5 |
Correct |
304 ms |
10988 KB |
Output is correct |
| 6 |
Correct |
688 ms |
17056 KB |
Output is correct |
| 7 |
Correct |
943 ms |
14744 KB |
Output is correct |
| 8 |
Correct |
1032 ms |
35336 KB |
Output is correct |
| 9 |
Correct |
1962 ms |
19948 KB |
Output is correct |
| 10 |
Correct |
2418 ms |
50088 KB |
Output is correct |
| 11 |
Correct |
2633 ms |
19692 KB |
Output is correct |
| 12 |
Correct |
1126 ms |
22140 KB |
Output is correct |
| 13 |
Correct |
1653 ms |
22836 KB |
Output is correct |
| 14 |
Correct |
1872 ms |
28972 KB |
Output is correct |
| 15 |
Correct |
2440 ms |
29020 KB |
Output is correct |
| 16 |
Correct |
2609 ms |
37988 KB |
Output is correct |
| 17 |
Correct |
2433 ms |
42760 KB |
Output is correct |
