Submission #1202034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202034		NikoBaotic	Regions (IOI09_regions)	C++20	30 / 100	8102 ms	39812 KiB

regions

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 200100;
const int R1 = 510;
const int R2 = 25010;
const int T = 200;
const int CNT = N / T + 10;
const int off = 1 << 18;
const int SZ = N / 64 + 10;

class Pref {
public:
	int pref[SZ];
	ll bits[SZ];

	Pref(vector<int> &v) {
		memset(bits, 0, sizeof bits);
		memset(pref, 0, sizeof pref);

		for (int x : v) {
			int pos = x / 64;
			int ost = x % 64;	

			bits[pos] |= 1 << ost;
		}

		for (int i = 0; i < SZ - 1; i++) {
			pref[i + 1] = pref[i] + __builtin_popcount(bits[i]);
		}
	}

	int query(int l, int r) {
		int pos1 = l / 64;
		int pos2 = r / 64;

		int ost1 = l % 64;
		int ost2 = r % 64;

		int ans = max(0, pref[pos2] - pref[pos1 + 1]);
		
		for (int i = ost1; i < 64; i++) {
			if ((1LL << i) & bits[pos1]) ans++;
		}
		
		for (int i = 0; i <= ost2; i++) {
			if ((1LL << i) & bits[pos2]) ans++;
		}

		return ans;
	}
};

int BIT[N];

void updateAt(int ind, int delta) {
	for (int i = ind + 1; ind < N; i += i&-i) {
		BIT[ind] += delta;
	}
}

ll queryAt(int ind) {
	ll sum = 0;

	for (int i = ind + 1; ind > 0; i -= i&-i) {
		sum += BIT[i];
	}

	return sum;
}

ll query(int l, int r) {
	return queryAt(r) - queryAt(l - 1);
}

void update(int l, int r, int delta) {
	updateAt(l, delta);
	updateAt(r + 1, delta);
}

int n, r, q;
int h[N];
int par[N];
vector<int> chi[N];
vector<int> emp[R2];
int in[N];
int out[N];
int timer;
int cnt[R1][R1];
Pref* vel[CNT];
map<int, int> conv;

vector<int>* dfs(int node) {
	vector<int>* cur = nullptr;

	for (int u : chi[node]) {
		vector<int>* v = dfs(u);

		if (cur == nullptr) {
			cur = v;
		} else {
			for (int i = 1; i < R1; i++) {
				(*cur)[i] += (*v)[i];
			}

			delete(v);
		}
	}
	
	if (sz(chi[node]) == 0) {
		cur = new vector<int>(R1);
	}
	
	for (int i = 1; i < R1; i++) {
		cnt[h[node]][i] += (*cur)[i];
	}

	(*cur)[h[node]]++;

	return cur;
}

void dfs2(int node) {
	timer++;
	in[node] = timer;

	for (int u : chi[node]) {
		dfs2(u);
	}

	out[node] = timer;
}

int main() {
	FIO;

	cin >> n >> r >> q;
	
	for (int i = 1; i <= n; i++) {
		if (i != 1) {
			cin >> par[i];

			chi[par[i]].pb(i);
		}

		cin >> h[i];
		emp[h[i]].pb(i);
	}

	if (r <= 500) {
		dfs(1);

		for (int i = 0; i < q; i++) {
			int r1, r2;
			cin >> r1 >> r2;

			int ans = cnt[r1][r2];

			cout << ans << endl;
		}
	} else {
		dfs2(1);

		int cur = 1;

		for (int i = 1; i <= r; i++) {
			if (sz(emp[i]) >= T) {
				conv[i] = cur;
				vel[cur] = new Pref(emp[i]);
				cur++;
			}
		}

		for (int i = 0; i < q; i++) {
			int r1, r2;
			cin >> r1 >> r2;

			int ans = 0;

			if (conv[r2] == 0) {
				for (int x : emp[r2]) {
					update(in[x], in[x], 1);
				}

				for (int x : emp[r1]) {
					ans += query(in[x], out[x]);
				}

				for (int x : emp[r2]) {
					update(in[x], in[x], -1);
				}
				
			} else {
				int ptr = conv[r2];

				for (int x : emp[r1]) {
					ans += vel[ptr]->query(in[x], out[x]);
				}
			}

			cout << ans << endl;
		}
	}

	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 85