| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 394208 |
2021-04-26T06:12:07 Z |
Berted |
Regions (IOI09_regions) |
C++14 |
|
8000 ms |
82852 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 = 250;
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[20][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 |
4 ms |
5576 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5576 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5704 KB |
Output is correct |
| 4 |
Correct |
10 ms |
5832 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5960 KB |
Output is correct |
| 6 |
Correct |
21 ms |
7116 KB |
Output is correct |
| 7 |
Correct |
32 ms |
6600 KB |
Output is correct |
| 8 |
Correct |
48 ms |
6980 KB |
Output is correct |
| 9 |
Correct |
73 ms |
8136 KB |
Output is correct |
| 10 |
Correct |
122 ms |
8776 KB |
Output is correct |
| 11 |
Correct |
174 ms |
9544 KB |
Output is correct |
| 12 |
Correct |
254 ms |
10988 KB |
Output is correct |
| 13 |
Correct |
210 ms |
10996 KB |
Output is correct |
| 14 |
Correct |
213 ms |
11960 KB |
Output is correct |
| 15 |
Correct |
237 ms |
16796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1024 ms |
21900 KB |
Output is correct |
| 2 |
Correct |
961 ms |
21408 KB |
Output is correct |
| 3 |
Correct |
2035 ms |
26512 KB |
Output is correct |
| 4 |
Correct |
326 ms |
16140 KB |
Output is correct |
| 5 |
Correct |
558 ms |
20280 KB |
Output is correct |
| 6 |
Correct |
872 ms |
23500 KB |
Output is correct |
| 7 |
Correct |
1233 ms |
30400 KB |
Output is correct |
| 8 |
Correct |
1810 ms |
40548 KB |
Output is correct |
| 9 |
Correct |
5178 ms |
53092 KB |
Output is correct |
| 10 |
Correct |
6293 ms |
70792 KB |
Output is correct |
| 11 |
Execution timed out |
8023 ms |
68648 KB |
Time limit exceeded |
| 12 |
Correct |
4320 ms |
61172 KB |
Output is correct |
| 13 |
Correct |
5758 ms |
61672 KB |
Output is correct |
| 14 |
Correct |
5625 ms |
66584 KB |
Output is correct |
| 15 |
Execution timed out |
8048 ms |
75520 KB |
Time limit exceeded |
| 16 |
Correct |
5618 ms |
82852 KB |
Output is correct |
| 17 |
Correct |
5786 ms |
77396 KB |
Output is correct |
