oj.uz

Submission #394210

# Submission time Handle Problem Language Result Execution time Memory
394210 2021-04-26T06:15:43 Z Berted Regions (IOI09_regions) C++14
100 / 100
 4745 ms 126864 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 = 700;

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 4 ms 5576 KB Output is correct
2 Correct 3 ms 5576 KB Output is correct
3 Correct 6 ms 5704 KB Output is correct
4 Correct 9 ms 5756 KB Output is correct
5 Correct 13 ms 5960 KB Output is correct
6 Correct 19 ms 7112 KB Output is correct
7 Correct 37 ms 6600 KB Output is correct
8 Correct 48 ms 6984 KB Output is correct
9 Correct 60 ms 8392 KB Output is correct
10 Correct 121 ms 9848 KB Output is correct
11 Correct 126 ms 9664 KB Output is correct
12 Correct 147 ms 12224 KB Output is correct
13 Correct 164 ms 11420 KB Output is correct
14 Correct 209 ms 11968 KB Output is correct
15 Correct 277 ms 16832 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 21968 KB Output is correct
2 Correct 947 ms 21440 KB Output is correct
3 Correct 1260 ms 26560 KB Output is correct
4 Correct 438 ms 24992 KB Output is correct
5 Correct 674 ms 30932 KB Output is correct
6 Correct 935 ms 37676 KB Output is correct
7 Correct 1534 ms 49752 KB Output is correct
8 Correct 2009 ms 60000 KB Output is correct
9 Correct 3696 ms 81328 KB Output is correct
10 Correct 3915 ms 114824 KB Output is correct
11 Correct 4745 ms 112712 KB Output is correct
12 Correct 3174 ms 91224 KB Output is correct
13 Correct 3409 ms 91620 KB Output is correct
14 Correct 3779 ms 103476 KB Output is correct
15 Correct 4082 ms 119444 KB Output is correct
16 Correct 4259 ms 126864 KB Output is correct
17 Correct 4558 ms 114436 KB Output is correct