Submission #1201962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201962		NikoBaotic	Regions (IOI09_regions)	C++20	10 / 100	346 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 {
	ll val, lazy;
	node *l, *r;
	int x, y;

	node(ll _val, int _x, int _y) : val(_val), x(_x), y(_y) {
		lazy = 0;
		l = nullptr;
		r = nullptr;
	}
};

void prop(node *no) {
	no->val += no->lazy;

	int mid = (no->x + no->y) / 2;

	if (no->x != no->y) {
		if (no->l == nullptr) no->l = new node(0, no->x, mid);
		if (no->r == nullptr) no->r = new node(0, mid + 1, no->y);

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

	no->lazy = 0;
}

void update(node *no, int l, int r, int delta) {
	if (no->x > r or l > no->y) return;
	if (l <= no->x and no->y <= r) {
		no->lazy += delta;
		prop(no);
		return;
	}

	prop(no);

	update(no->l, l, r, delta);
	update(no->r, l, r, delta);

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

ll query(node *no, int tar) {
	if (no->x > tar or tar > no->y) return 0;

	prop(no);

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

	return query(no->l, tar) + query(no->r, tar);
}

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, 0, off - 1);
	}

	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;

		ll ans = 0;

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

		cout << ans << endl;
	}

	return 0;
}

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