Submission #394203

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394203	2021-04-26T05:58:29 Z	Berted	Regions (IOI09_regions)	C++14	55 / 100	2072 ms	131072 KB

regions

#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[18][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); 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, 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	5 ms	5752 KB	Output is correct
4	Correct	9 ms	5832 KB	Output is correct
5	Correct	13 ms	5960 KB	Output is correct
6	Correct	29 ms	7112 KB	Output is correct
7	Correct	18 ms	6600 KB	Output is correct
8	Correct	55 ms	6984 KB	Output is correct
9	Correct	77 ms	8424 KB	Output is correct
10	Correct	131 ms	9760 KB	Output is correct
11	Correct	75 ms	9760 KB	Output is correct
12	Correct	135 ms	12216 KB	Output is correct
13	Correct	215 ms	11440 KB	Output is correct
14	Correct	188 ms	11884 KB	Output is correct
15	Correct	281 ms	16832 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1036 ms	21896 KB	Output is correct
2	Correct	1057 ms	21408 KB	Output is correct
3	Correct	1687 ms	26560 KB	Output is correct
4	Correct	503 ms	21032 KB	Output is correct
5	Correct	656 ms	26200 KB	Output is correct
6	Correct	972 ms	31448 KB	Output is correct
7	Correct	1317 ms	41188 KB	Output is correct
8	Correct	1812 ms	51380 KB	Output is correct
9	Runtime error	1453 ms	131072 KB	Execution killed with signal 11
10	Runtime error	1720 ms	131072 KB	Execution killed with signal 11
11	Runtime error	2072 ms	131072 KB	Execution killed with signal 11
12	Runtime error	1895 ms	131072 KB	Execution killed with signal 11
13	Runtime error	1781 ms	131072 KB	Execution killed with signal 11
14	Runtime error	1881 ms	131072 KB	Execution killed with signal 11
15	Runtime error	1946 ms	131072 KB	Execution killed with signal 11
16	Runtime error	2064 ms	131072 KB	Execution killed with signal 11
17	Runtime error	1962 ms	131072 KB	Execution killed with signal 11