// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5, maxr = 25e3+5, sq = 200, sq_ = 1e3+5;
int n, q, t = 0, cur = 0, re[maxn], id[maxr], cnt[sq_], res[sq_][maxr], in[maxn], out[maxn];
vector <int> adj[maxn], oc[maxr], vec;
vector <pii> seg[maxn];
void dfs(int v = 0) {
in[v] = t++; vec.pb(v);
if (oc[re[v]].size() >= sq) cnt[id[re[v]]]++;
for (int i = 0; i < sq_; i++) res[i][re[v]] += cnt[i];
for (int u : adj[v]) dfs(u);
if (oc[re[v]].size() >= sq) cnt[id[re[v]]]--;
out[v] = t;
}
void build(int l = 0, int r = n, int id = 1) {
if (l+1 == r) {
seg[id].pb(mp(-1, 0));
seg[id].pb(mp(re[vec[l]], 0));
return;
}
int mid = (l+r)/2;
build(l, mid, id*2), build(mid, r, id*2+1);
int p1 = 1, p2 = 1;
seg[id].pb(mp(-1, 0));
while (p1 < mid-l+1 or p2 < r-mid+1) {
if (p1 == mid-l+1) {
seg[id].pb(mp(seg[id*2+1][p2].F, seg[id].back().S));
p2++;
}
else if (p2 == r-mid+1) {
seg[id].pb(mp(seg[id*2][p1].F, seg[id].back().S+1));
p1++;
}
else {
if (seg[id*2][p1].F < seg[id*2+1][p2].F) {
seg[id].pb(mp(seg[id*2][p1].F, seg[id].back().S+1));
p1++;
}
else {
seg[id].pb(mp(seg[id*2+1][p2].F, seg[id].back().S));
p2++;
}
}
}
}
int get(int s, int e, int i, int j, int l = 0, int r = n, int id = 1) {
if (j == i) return 0;
if (s <= l and r <= e) return j-i;
int mid = (l+r)/2, ans = 0;
assert(i >= 0);
assert(j >= 0);
if (s < mid) ans += get(s, e, seg[id][i].S, seg[id][j].S, l, mid, id*2);
if (e > mid) ans += get(s, e, i-seg[id][i].S, j-seg[id][j].S, mid, r, id*2+1);
return ans;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q >> q;
cin >> re[0]; re[0]--;
oc[re[0]].pb(0);
for (int i = 1; i < n; i++) {
int p; cin >> p >> re[i]; re[i]--;
adj[--p].pb(i);
oc[re[i]].pb(i);
}
for (int i = 0; i < maxr; i++) {
if (oc[i].size() >= sq) id[i] = cur++;
}
dfs();
build();
// for (pii p : seg[1]) cout << p.F << ' ' << p.S << '\n';
while (q--) {
int r1, r2; cin >> r1 >> r2; r1--, r2--;
if (oc[r1].size() >= sq) cout << res[id[r1]][r2];
else {
int ans = 0;
int l = lower_bound(all(seg[1]), mp(r2, -inf))-seg[1].begin()-1;
int r = upper_bound(all(seg[1]), mp(r2, inf))-seg[1].begin()-1;
// cout << l << ' ' << r << '\n';
if (l != seg[1].size()) {
for (int v : oc[r1]) ans += get(in[v], out[v], l, r);
}
cout << ans;
}
cout << endl;
}
return 0;
}
Compilation message
regions.cpp: In function 'int32_t main()':
regions.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if (l != seg[1].size()) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
109400 KB |
Output is correct |
| 2 |
Correct |
14 ms |
109400 KB |
Output is correct |
| 3 |
Correct |
13 ms |
109332 KB |
Output is correct |
| 4 |
Correct |
15 ms |
109400 KB |
Output is correct |
| 5 |
Correct |
16 ms |
109400 KB |
Output is correct |
| 6 |
Correct |
20 ms |
109400 KB |
Output is correct |
| 7 |
Correct |
29 ms |
109656 KB |
Output is correct |
| 8 |
Correct |
32 ms |
109656 KB |
Output is correct |
| 9 |
Correct |
50 ms |
111020 KB |
Output is correct |
| 10 |
Correct |
80 ms |
112024 KB |
Output is correct |
| 11 |
Correct |
150 ms |
112952 KB |
Output is correct |
| 12 |
Correct |
185 ms |
115052 KB |
Output is correct |
| 13 |
Correct |
228 ms |
115060 KB |
Output is correct |
| 14 |
Correct |
405 ms |
116464 KB |
Output is correct |
| 15 |
Correct |
545 ms |
122952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
187 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
190 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Correct |
334 ms |
116672 KB |
Output is correct |
| 5 |
Correct |
521 ms |
121840 KB |
Output is correct |
| 6 |
Correct |
526 ms |
122868 KB |
Output is correct |
| 7 |
Runtime error |
458 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
539 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
1187 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
1299 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
1594 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
1299 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
1225 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
1255 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
1300 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
1113 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
1265 ms |
131072 KB |
Execution killed with signal 9 |
