oj.uz

Submission #394200

# Submission time Handle Problem Language Result Execution time Memory
394200 2021-04-26T05:50:53 Z Berted Regions (IOI09_regions) C++14
100 / 100
 7894 ms 126472 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, SGSZ = (1 << 19) + 5;

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];
vector<pii> seg[SGSZ], 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, bool b)
{
	if (L <= R)
	{
		seg[idx].assign(R - L + 1, make_pair(0, 0));
		for (int i = L; i <= R; i++) seg[idx][i - L] = make_pair(ord[i], i);

		if (b) sort(seg[idx].begin(), seg[idx].end());
		else sort(seg[idx].begin(), seg[idx].end(), greater<pii>());

		if (L < R)
		{
			int M = L + R >> 1;
			build(2 * idx, L, M, 0);
			build(2 * idx + 1, M + 1, R, 1);
		}
	}
}

int query(int idx, int L, int R, 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 R = upper_bound(seg[idx].begin(), seg[idx].end(), make_pair(v, r));
			auto L = lower_bound(seg[idx].begin(), seg[idx].end(), make_pair(v, l));
			//cerr << "ANS1: " << L - seg[idx].begin() << " " << R - seg[idx].begin() << "\n";
			return R - L;
		}
		else if (!b && r == R)
		{
			auto R = upper_bound(seg[idx].begin(), seg[idx].end(), make_pair(v, l), greater<pii>());
			auto L = lower_bound(seg[idx].begin(), seg[idx].end(), make_pair(v, r), greater<pii>());
			//cerr << "ANS0: " << L - seg[idx].begin() << " " << R - seg[idx].begin() << "\n";
			return R - L;
		}
		else
		{
			int M = L + R >> 1;
			return query(2 * idx, L, M, 0, l, r, v) + query(2 * idx + 1, M + 1, R, 1, l, r, v);
		}
	}
	return 0;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.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;}

	DFS(0, -1);
	
	//for (int i = 0; i < N; i++) cerr << ord[i] << " "; cerr << "\n";

	build(1, 0, N - 1, 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, 1, L[u] + 1, R[u], b);
			cout << res << endl;
		}
	}

	return 0;
}

Compilation message

regions.cpp: In function 'void build(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, 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 11 ms 17864 KB Output is correct
2 Correct 13 ms 17864 KB Output is correct
3 Correct 12 ms 18020 KB Output is correct
4 Correct 16 ms 17992 KB Output is correct
5 Correct 15 ms 18204 KB Output is correct
6 Correct 35 ms 19424 KB Output is correct
7 Correct 29 ms 18888 KB Output is correct
8 Correct 59 ms 19272 KB Output is correct
9 Correct 57 ms 20812 KB Output is correct
10 Correct 97 ms 22336 KB Output is correct
11 Correct 136 ms 22428 KB Output is correct
12 Correct 145 ms 24988 KB Output is correct
13 Correct 165 ms 24496 KB Output is correct
14 Correct 176 ms 25140 KB Output is correct
15 Correct 297 ms 30364 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 36544 KB Output is correct
2 Correct 1031 ms 36252 KB Output is correct
3 Correct 1454 ms 41688 KB Output is correct
4 Correct 524 ms 34276 KB Output is correct
5 Correct 730 ms 39468 KB Output is correct
6 Correct 736 ms 45284 KB Output is correct
7 Correct 1503 ms 55392 KB Output is correct
8 Correct 1840 ms 66912 KB Output is correct
9 Correct 4209 ms 85428 KB Output is correct
10 Correct 4770 ms 112752 KB Output is correct
11 Correct 7894 ms 112092 KB Output is correct
12 Correct 3247 ms 96248 KB Output is correct
13 Correct 4061 ms 96648 KB Output is correct
14 Correct 4037 ms 105964 KB Output is correct
15 Correct 5491 ms 118976 KB Output is correct
16 Correct 4246 ms 126472 KB Output is correct
17 Correct 4046 ms 117004 KB Output is correct