# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
988448 |
2024-05-24T17:41:21 Z |
orcslop |
Regions (IOI09_regions) |
C++17 |
|
3994 ms |
34292 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>
const int MAXR = 25005;
const int MAXN = 2e5 + 5;
const int RT = 450;
int n, r, q, timer;
int h[MAXN];
int tin[MAXN];
int subs[MAXN];
int pre[RT][MAXN];
int tree[2 * MAXN];
map<int, int> mp;
vector<int> adj[MAXN];
vector<int> eul[MAXR], occ[MAXR];
void dfs(int node, int prev){
subs[node] = 1;
tin[node] = timer++;
for(auto x : adj[node]){
if(x == prev) continue;
dfs(x, node);
subs[node] += subs[x];
}
}
int query(int a, int b){
a += n;
b += n;
int s = 0;
while(a <= b){
if(a % 2 == 1) s += tree[a++];
if(b % 2 == 0) s += tree[b--];
a /= 2; b /= 2;
}
return s;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> r >> q;
cin >> h[0];
occ[h[0]].pb(0);
for(int i = 1; i < n; i++){
int x;
cin >> x >> h[i];
adj[--x].pb(i);
adj[i].pb(x);
occ[h[i]].pb(i);
}
dfs(0, -1);
for(int i = 1; i < MAXR; i++){
for(auto x : occ[i]) eul[i].pb(tin[x]);
sort(all(eul[i]));
sort(all(occ[i]), [](int &a, int &b){
return tin[a] < tin[b];
});
if(occ[i].size() >= RT) {
int index = 0;
for(int j = 0; j < n; j++){
if(index < eul[i].size() && j == eul[i][index]){
tree[j + n] = 1;
index++;
}
else tree[j + n] = 0;
}
for(int j = n - 1; j >= 0; j--){
tree[j] = tree[2 * j] + tree[2 * j + 1];
}
for(int j = 1; j < MAXR; j++){
for(auto x : occ[j]){
pre[mp.size()][j] += query(tin[x], tin[x] + subs[x] - 1);
}
}
mp[i] = mp.size();
}
}
for(int i = 0; i < q; i++){
int a, b;
cin >> a >> b;
if(occ[a].size() >= RT) cout << pre[mp[a]][b] << endl;
else{
int ans = 0;
for(auto x : occ[a]){
auto lb = lower_bound(all(eul[b]), tin[x]);
auto ub = upper_bound(all(eul[b]), tin[x] + subs[x] - 1);
ans += ub - lb;
}
cout << ans << endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int32_t main()':
regions.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(index < eul[i].size() && j == eul[i][index]){
| ~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6744 KB |
Output is correct |
2 |
Correct |
4 ms |
6232 KB |
Output is correct |
3 |
Correct |
5 ms |
6232 KB |
Output is correct |
4 |
Correct |
5 ms |
6232 KB |
Output is correct |
5 |
Correct |
8 ms |
6232 KB |
Output is correct |
6 |
Correct |
11 ms |
6232 KB |
Output is correct |
7 |
Correct |
13 ms |
6744 KB |
Output is correct |
8 |
Correct |
19 ms |
6744 KB |
Output is correct |
9 |
Correct |
32 ms |
7000 KB |
Output is correct |
10 |
Correct |
44 ms |
7256 KB |
Output is correct |
11 |
Correct |
64 ms |
7644 KB |
Output is correct |
12 |
Correct |
88 ms |
7740 KB |
Output is correct |
13 |
Correct |
102 ms |
7544 KB |
Output is correct |
14 |
Correct |
163 ms |
8492 KB |
Output is correct |
15 |
Correct |
184 ms |
12136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1409 ms |
12204 KB |
Output isn't correct |
2 |
Incorrect |
1545 ms |
11568 KB |
Output isn't correct |
3 |
Incorrect |
2117 ms |
14580 KB |
Output isn't correct |
4 |
Correct |
173 ms |
8536 KB |
Output is correct |
5 |
Correct |
224 ms |
10840 KB |
Output is correct |
6 |
Incorrect |
532 ms |
14048 KB |
Output isn't correct |
7 |
Incorrect |
1147 ms |
11812 KB |
Output isn't correct |
8 |
Incorrect |
1778 ms |
22516 KB |
Output isn't correct |
9 |
Correct |
1591 ms |
17268 KB |
Output is correct |
10 |
Incorrect |
3994 ms |
30412 KB |
Output isn't correct |
11 |
Correct |
2653 ms |
19016 KB |
Output is correct |
12 |
Incorrect |
903 ms |
18860 KB |
Output isn't correct |
13 |
Incorrect |
1336 ms |
19940 KB |
Output isn't correct |
14 |
Incorrect |
1815 ms |
21716 KB |
Output isn't correct |
15 |
Incorrect |
2330 ms |
25276 KB |
Output isn't correct |
16 |
Incorrect |
2269 ms |
34292 KB |
Output isn't correct |
17 |
Incorrect |
2677 ms |
34068 KB |
Output isn't correct |