oj.uz

답안 #394203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394203 2021-04-26T05:58:29 Z Berted Regions (IOI09_regions) C++14
55 / 100
 2072 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 = 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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