| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 394211 |
2021-04-26T06:18:09 Z |
Berted |
Regions (IOI09_regions) |
C++14 |
|
5093 ms |
131076 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;
const int SZ = 750;
int N, K, Q, A[200001], L[200001], R[200001], ord[200001], ti = 0;
int num[25001], tp[SZ], cnt[SZ][25001];
vector<int> adj[200001], idx[25001];
pii seg[19][200001];
vector<pii> temp;
void DFS(int u, int p)
{
for (int i = 0; i < SZ && i < K; i++) {cnt[i][A[u]] += tp[i];}
if (num[A[u]] < SZ) {tp[num[A[u]]]++;}
L[u] = R[u] = ti; ord[ti++] = A[u];
for (const int &v : adj[u]) {DFS(v, u); R[u] = R[v];}
if (num[A[u]] < SZ) {tp[num[A[u]]]--;}
//cerr << "DFS: " << u << ", " << p << " - " << L[u] << ", " << R[u] << "\n";
}
void build(int idx, int L, int R, int lvl, bool b)
{
if (L <= R)
{
for (int i = L; i <= R; i++) seg[lvl][i] = make_pair(ord[i], i);
if (b) sort(seg[lvl] + L, seg[lvl] + R + 1);
else sort(seg[lvl] + L, seg[lvl] + R + 1, greater<pii>());
if (L < R)
{
int M = L + R >> 1;
build(2 * idx, L, M, lvl + 1, 0);
build(2 * idx + 1, M + 1, R, lvl + 1, 1);
}
}
}
int query(int idx, int L, int R, int lvl, bool b, int l, int r, int v)
{
l = max(L, l); r = min(R, r);
if (l <= r)
{
//cerr << "CALL: " << idx << " " << L << " " << R << " " << b << " " << l << " " << r << " " << v << "\n";
if (b && l == L)
{
auto itR = upper_bound(seg[lvl] + L, seg[lvl] + R + 1, make_pair(v, r));
auto itL = lower_bound(seg[lvl] + L, seg[lvl] + R + 1, make_pair(v, l));
//cerr << "ANS1: " << L - seg[idx].begin() << " " << R - seg[idx].begin() << "\n";
return itR - itL;
}
else if (!b && r == R)
{
auto itR = upper_bound(seg[lvl] + L, seg[lvl] + R + 1, make_pair(v, l), greater<pii>());
auto itL = lower_bound(seg[lvl] + L, seg[lvl] + R + 1, make_pair(v, r), greater<pii>());
//cerr << "ANS0: " << L - seg[idx].begin() << " " << R - seg[idx].begin() << "\n";
return itR - itL;
}
else
{
int M = L + R >> 1;
return query(2 * idx, L, M, lvl + 1, 0, l, r, v) + query(2 * idx + 1, M + 1, R, lvl + 1, 1, l, r, v);
}
}
return 0;
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0);
cin >> N >> K >> Q;
for (int i = 0; i < N; i++)
{
if (i) {int p; cin >> p; adj[p - 1].push_back(i);}
cin >> A[i]; A[i]--;
idx[A[i]].push_back(i);
}
for (int i = 0; i < K; i++) {temp.push_back({idx[i].size(), i}); num[i] = -1;}
sort(temp.begin(), temp.end(), greater<pii>());
for (int i = 0; i < K; i++) {num[temp[i].snd] = i;}
temp.clear();
DFS(0, -1);
for (int i = 0; i < N; i++) adj[i].clear();
//for (int i = 0; i < N; i++) cerr << ord[i] << " "; cerr << "\n";
build(1, 0, N - 1, 0, 1);
for (int i = 0; i < Q; i++)
{
int a, b; cin >> a >> b; a--; b--;
if (num[a] < SZ) cout << cnt[num[a]][b] << endl;
else
{
int res = 0;
for (const int &u : idx[a]) res += query(1, 0, N - 1, 0, 1, L[u] + 1, R[u], b);
cout << res << endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'void build(int, int, int, int, bool)':
regions.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int M = L + R >> 1;
| ~~^~~
regions.cpp: In function 'int query(int, int, int, int, bool, int, int, int)':
regions.cpp:74:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int M = L + R >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5580 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5576 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5760 KB |
Output is correct |
| 4 |
Correct |
10 ms |
5832 KB |
Output is correct |
| 5 |
Correct |
13 ms |
5960 KB |
Output is correct |
| 6 |
Correct |
25 ms |
7112 KB |
Output is correct |
| 7 |
Correct |
42 ms |
6600 KB |
Output is correct |
| 8 |
Correct |
51 ms |
6984 KB |
Output is correct |
| 9 |
Correct |
51 ms |
8392 KB |
Output is correct |
| 10 |
Correct |
121 ms |
9800 KB |
Output is correct |
| 11 |
Correct |
109 ms |
9588 KB |
Output is correct |
| 12 |
Correct |
146 ms |
12180 KB |
Output is correct |
| 13 |
Correct |
214 ms |
11456 KB |
Output is correct |
| 14 |
Correct |
163 ms |
11968 KB |
Output is correct |
| 15 |
Correct |
262 ms |
16840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
894 ms |
22012 KB |
Output is correct |
| 2 |
Correct |
905 ms |
21400 KB |
Output is correct |
| 3 |
Correct |
1708 ms |
26520 KB |
Output is correct |
| 4 |
Correct |
443 ms |
25924 KB |
Output is correct |
| 5 |
Correct |
664 ms |
32120 KB |
Output is correct |
| 6 |
Correct |
1118 ms |
39248 KB |
Output is correct |
| 7 |
Correct |
1908 ms |
51956 KB |
Output is correct |
| 8 |
Correct |
1982 ms |
62160 KB |
Output is correct |
| 9 |
Correct |
4059 ms |
84468 KB |
Output is correct |
| 10 |
Correct |
3918 ms |
119720 KB |
Output is correct |
| 11 |
Correct |
5093 ms |
117568 KB |
Output is correct |
| 12 |
Correct |
3527 ms |
94516 KB |
Output is correct |
| 13 |
Correct |
3581 ms |
94948 KB |
Output is correct |
| 14 |
Correct |
4351 ms |
107592 KB |
Output is correct |
| 15 |
Correct |
4541 ms |
124436 KB |
Output is correct |
| 16 |
Runtime error |
2770 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Correct |
4666 ms |
118560 KB |
Output is correct |
