oj.uz

Submission #394209

# Submission time Handle Problem Language Result Execution time Memory
394209 2021-04-26T06:14:03 Z Berted Regions (IOI09_regions) C++14
100 / 100
 7081 ms 107472 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 = 500;

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;
      |            ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 6 ms 5648 KB Output is correct
4 Correct 9 ms 5836 KB Output is correct
5 Correct 13 ms 5960 KB Output is correct
6 Correct 27 ms 7112 KB Output is correct
7 Correct 42 ms 6600 KB Output is correct
8 Correct 49 ms 6984 KB Output is correct
9 Correct 61 ms 8432 KB Output is correct
10 Correct 98 ms 9792 KB Output is correct
11 Correct 95 ms 9672 KB Output is correct
12 Correct 164 ms 12224 KB Output is correct
13 Correct 183 ms 11516 KB Output is correct
14 Correct 207 ms 11968 KB Output is correct
15 Correct 211 ms 16832 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 21924 KB Output is correct
2 Correct 907 ms 21336 KB Output is correct
3 Correct 943 ms 26560 KB Output is correct
4 Correct 459 ms 20928 KB Output is correct
5 Correct 561 ms 26188 KB Output is correct
6 Correct 925 ms 31368 KB Output is correct
7 Correct 1344 ms 41236 KB Output is correct
8 Correct 1884 ms 51408 KB Output is correct
9 Correct 3906 ms 68776 KB Output is correct
10 Correct 4280 ms 95364 KB Output is correct
11 Correct 7081 ms 93260 KB Output is correct
12 Correct 3136 ms 77896 KB Output is correct
13 Correct 3693 ms 78372 KB Output is correct
14 Correct 3616 ms 87024 KB Output is correct
15 Correct 5113 ms 99964 KB Output is correct
16 Correct 3760 ms 107472 KB Output is correct
17 Correct 4005 ms 98016 KB Output is correct