제출 #700887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700887		badont	Regions (IOI09_regions)	C++17	100 / 100	3858 ms	58760 KiB

regions

#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

template<typename T>
struct fen {
	vector<T> tr;
	ll mxn;

	fen(ll sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(ll g, T k) {
		g++;
		assert(g != 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(ll g) {
		g++;
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(ll l, ll r) { return ge(r) - ge(l - 1); }

	//maxi and mini only work with positive numbers
	ll maxi(T k) {
		//max i such that ge(i) <= k.
		//log(n) vs log^2(n) binary search
		T running = 0; ll res = 0;
		ll lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] > k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res;
	}

	ll mini(T k) {
		//kth order statistic
		T running = 0; ll res = 0;
		ll lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] >= k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res + 1;
	}
};

//var 
ll T;

void solve() {
	int n, r, q;
	cin >> n >> r >> q;

	vector<int> region(n), parent(n);
	F0R (i, n) {
		if (i) cin >> parent[i];
		parent[i]--;
		cin >> region[i];
		region[i]--;
	}

	vector adj(n, vector<int>());
	FOR (i, n - 1) {
		adj[parent[i]].pb(i);
	}
	vector<int> tin(n), tout(n);

	int cc = 0;
	auto dfs = [&](auto dfs, int g, int p) -> void {
		tin[g] = cc++;
		for (auto u : adj[g]) if (u != p) {
			dfs(dfs, u, g);
		}
		tout[g] = cc++;
	};

	dfs(dfs, 0, -1);
	

	vector in_region(r, vector<int>());
	F0R (i, n) in_region[region[i]].pb(i);
	region.clear();

	constexpr int B = 250;
	// at most n / B greater than B

	vector<short> GB;
	F0R (i, r) if ((int)in_region[i].size() > B) {
		GB.pb(i);
	}
	
	//debug(tin, tout);

	sort(all(GB));
	auto big_region = [&](short x) -> int {
		auto iter = lower_bound(all(GB), x);
		if (iter == GB.end() or *iter != x) return -1;
		return iter - GB.begin();
	};

	//debug(in_region);
	vector region_locs(r, vector<int>());
	F0R (i, r) {
		for (auto node : in_region[i]) {
			region_locs[i].pb(tin[node]);
		}
		sort(all(region_locs[i]));
	}

	int M = (int)GB.size();
	vector dp(M, vector<int>(r));

	fen<int> tree(cc);
	F0R (i1, M) {
		int r1 = GB[i1];
		vector<int> pf(cc);

		for (auto node : in_region[r1]) {
			pf[tin[node]]++;
			pf[tout[node]]--;
		} 

		FOR (i, cc - 1) pf[i] += pf[i - 1];
		F0R (r2, r) {
			for (auto node : in_region[r2]) {
				dp[i1][r2] += pf[tin[node]];
			}
		}
	}

	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;

		int get_1 = big_region(r1);
		if (get_1 == -1) {
			ll ans = 0;

			for (auto node : in_region[r1]) {
				auto iter_r = upper_bound(all(region_locs[r2]), tout[node]);
				auto iter_l = lower_bound(all(region_locs[r2]), tin[node]);
				ans += iter_r - iter_l;
			}
			cout << ans << endl;
		} else {
			cout << dp[get_1][r2] << endl;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

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