Submission #1201973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201973		NikoBaotic	Regions (IOI09_regions)	C++20	12 / 100	3159 ms	196608 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 R = 25000;
const int off = 1 << 18;

struct node {
	int val, lazy;
	node *l, *r;

	node(int _val) : val(_val) {
		lazy = 0;
		l = nullptr;
		r = nullptr;
	}
};

void prop(node *no, int x, int y) {
	if (no == nullptr) return;

	no->val += no->lazy;

	if (x != y and no->lazy) {
		if (no->l == nullptr) no->l = new node(0);
		if (no->r == nullptr) no->r = new node(0);

		no->l->lazy += no->lazy;
		no->r->lazy += no->lazy;
	}

	no->lazy = 0;
}

node* update(node *no, int l, int r, int delta, int x = 0, int y = off - 1) {
	if (x > r or l > y) return no;
	if (no == nullptr) no = new node(0);

	if (l <= x and y <= r) {
		no->lazy += delta;
		prop(no, x, y);
		return no;
	}

	prop(no, x, y);

	no->l = update(no->l, l, r, delta, x, (x + y) / 2);
	no->r = update(no->r, l, r, delta, (x + y) / 2 + 1, y);
	
	no->val = 0;

	if (no->l != nullptr) no->val += no->l->val;
	if (no->r != nullptr) no->val += no->r->val;

	return no;
}

int query(node *no, int tar, int x = 0, int y = off - 1) {
	if (no == nullptr) return 0;

	if (x > tar or tar > y) return 0;

	prop(no, x, y);

	if (tar == x and y == tar) return no->val;

	return query(no->l, tar, x, (x + y) / 2) + query(no->r, tar, (x + y) / 2 + 1, y);
}

int n, r, q;
int h[N];
int par[N];
vector<int> chi[N];
vector<int> emp[R];
node* tr[R];
int in[N];
int out[N];
int timer;

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

	for (int u : chi[node]) {
		dfs(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);
	}

	for (int i = 1; i <= r; i++) {
		tr[i] = new node(0);
	}

	dfs(1);

	for (int i = 1; i <= n; i++) {
		update(tr[h[i]], in[i], out[i], 1);
	}

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

		int ans = 0;

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

		cout << ans << endl;
	}

	return 0;
}

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