Submission #1132040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132040		ByeWorld	Regions (IOI09_regions)	C++20	55 / 100	8096 ms	30920 KiB

regions

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int SQRT = 100;
const int MAXA = 1e6;
const int MOD = 1e9+7;
const int INF = 1e9+10;
const int LOG = 21;
const ld EPS = 1e-12;

int n, r, k, a[MAXN];
vector <int> adj[MAXN], idx[MAXN];
int in[MAXN],out[MAXN],tim, par[MAXN];

void dfs(int nw){
	in[nw] = ++tim;
	for(auto nx : adj[nw]){
		dfs(nx);
	}
	out[nw] = tim;
}
struct seg {
	int st[2*MAXN];
	int que(int x){
		int te = 0;
		for(; x>=1; x-=(x&(-x))) te += st[x];
		return te;
	}
	void upd(int x,int y){
		for(;x<=2*MAXN-20;x+=(x&(-x)))
			st[x] += y;
	}
} A;
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>r>>k;
	cin >> a[1]; idx[a[1]].pb(1);
	for(int i=2; i<=n; i++){
		cin>>par[i]>>a[i]; adj[par[i]].pb(i);
		idx[a[i]].pb(i);
	}
	dfs(1);
	while(k--){
		int x, y; cin>>x>>y; // x di atas y
		int ans = 0;
		for(auto id : idx[y]) A.upd(in[id], 1);
		for(auto id : idx[x]) ans += A.que(out[id])-A.que(in[id]-1);
		for(auto id : idx[y]) A.upd(in[id], -1);
		cout << ans << endl;
	}
}

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