oj.uz

Submission #394204

# Submission time Handle Problem Language Result Execution time Memory
394204 2021-04-26T06:03:51 Z Berted Regions (IOI09_regions) C++14
55 / 100
 2110 ms 131072 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[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 3 ms 5704 KB Output is correct
3 Correct 6 ms 5704 KB Output is correct
4 Correct 9 ms 5832 KB Output is correct
5 Correct 10 ms 5960 KB Output is correct
6 Correct 27 ms 7112 KB Output is correct
7 Correct 35 ms 6600 KB Output is correct
8 Correct 34 ms 6984 KB Output is correct
9 Correct 75 ms 8136 KB Output is correct
10 Correct 109 ms 8768 KB Output is correct
11 Correct 130 ms 9544 KB Output is correct
12 Correct 229 ms 11072 KB Output is correct
13 Correct 259 ms 10940 KB Output is correct
14 Correct 258 ms 11936 KB Output is correct
15 Correct 269 ms 16852 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 21952 KB Output is correct
2 Correct 810 ms 21456 KB Output is correct
3 Correct 1958 ms 26436 KB Output is correct
4 Correct 388 ms 16076 KB Output is correct
5 Correct 617 ms 20268 KB Output is correct
6 Correct 875 ms 23492 KB Output is correct
7 Correct 1316 ms 30324 KB Output is correct
8 Correct 2110 ms 40548 KB Output is correct
9 Runtime error 797 ms 105008 KB Execution killed with signal 11
10 Runtime error 969 ms 131072 KB Execution killed with signal 11
11 Runtime error 1122 ms 131072 KB Execution killed with signal 11
12 Runtime error 958 ms 120776 KB Execution killed with signal 11
13 Runtime error 982 ms 121780 KB Execution killed with signal 11
14 Runtime error 1047 ms 131072 KB Execution killed with signal 11
15 Runtime error 1073 ms 131072 KB Execution killed with signal 11
16 Runtime error 1219 ms 131072 KB Execution killed with signal 11
17 Runtime error 1127 ms 131072 KB Execution killed with signal 11