oj.uz

Submission #394199

# Submission time Handle Problem Language Result Execution time Memory
394199 2021-04-26T05:50:13 Z Berted Regions (IOI09_regions) C++14
40 / 100
 8000 ms 77500 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 = 1, 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 14 ms 17864 KB Output is correct
4 Correct 17 ms 17872 KB Output is correct
5 Correct 17 ms 17992 KB Output is correct
6 Correct 33 ms 18120 KB Output is correct
7 Correct 52 ms 18108 KB Output is correct
8 Correct 69 ms 18248 KB Output is correct
9 Correct 100 ms 19144 KB Output is correct
10 Correct 165 ms 19908 KB Output is correct
11 Correct 324 ms 20964 KB Output is correct
12 Correct 411 ms 22412 KB Output is correct
13 Correct 401 ms 22724 KB Output is correct
14 Correct 941 ms 24256 KB Output is correct
15 Correct 896 ms 29152 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8095 ms 35512 KB Time limit exceeded
2 Execution timed out 8007 ms 35008 KB Time limit exceeded
3 Execution timed out 8095 ms 40248 KB Time limit exceeded
4 Correct 844 ms 24384 KB Output is correct
5 Correct 774 ms 27612 KB Output is correct
6 Correct 4493 ms 29560 KB Output is correct
7 Correct 7292 ms 33832 KB Output is correct
8 Correct 4732 ms 45256 KB Output is correct
9 Execution timed out 8019 ms 54064 KB Time limit exceeded
10 Execution timed out 8067 ms 63916 KB Time limit exceeded
11 Execution timed out 8100 ms 63268 KB Time limit exceeded
12 Execution timed out 8010 ms 62892 KB Time limit exceeded
13 Execution timed out 8080 ms 63288 KB Time limit exceeded
14 Execution timed out 8029 ms 64836 KB Time limit exceeded
15 Execution timed out 8037 ms 70052 KB Time limit exceeded
16 Execution timed out 8060 ms 77500 KB Time limit exceeded
17 Execution timed out 8098 ms 75844 KB Time limit exceeded