Submission #531801

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531801	2022-03-01T14:23:45 Z	akhan42	Regions (IOI09_regions)	C++17	100 / 100	6587 ms	119236 KB

regions

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 200 * 1000 + 10;
const int S = 100;


struct FenwBase {
	int n;
	int bit[MX] = {0};

	void upd(int i, int v) {
		for(i += 1; i <= n; i += i & -i)
			bit[i] += v;
	}

	int psum(int i) {
		int sum = 0;
		for(i += 1; i > 0; i -= i & -i)
			sum += bit[i];
		return sum;
	}
};


struct Fenw {
	FenwBase fb;

	Fenw(int n) {
		fb.n = n;
	}

	void update(int l, int r, int v) {
		fb.upd(l, v);
		fb.upd(r + 1, -v);
	}

	int at(int i) {
		return fb.psum(i);
	}
};


int n, R, Q;
vi gr[MX];
int e2r[MX];
vi r2es[MX];
int pc[S][MX];
int ct[MX];
vi regions;
int inv_reg[MX];
int tin[MX], tout[MX];
int timer = -1;
int pc2[S][MX];
int time2reg[MX];


bool cmp_reg(int r1, int r2) {
	return sz(r2es[r1]) > sz(r2es[r2]);
}


void dfs(int node = 0) {
	forn(i, min(R, S)) {
		int r = regions[i];
		pc[i][e2r[node]] += ct[r];
	}

	tin[node] = ++timer;
	time2reg[timer] = e2r[node];
	ct[e2r[node]] += 1;

	for(int nb: gr[node]) {
		dfs(nb);
	}

	ct[e2r[node]] -= 1;
	tout[node] = timer;
}


void solve() {
	cin >> n >> R >> Q;

	forn(i, n) {
		int r, p;
		if(i == 0) {
			cin >> r;
		} else {
			cin >> p >> r;
			p -= 1;
			gr[p].pb(i);
		}
		r--;
		e2r[i] = r;
		r2es[r].pb(i);
	}

	forn(i, R)
		regions.pb(i);

	sort(all(regions), cmp_reg);

	forn(i, R)
		inv_reg[regions[i]] = i;

	dfs();

	forn(i, min(R, S)) {
		int r = regions[i];

		forn(t, n) {
			pc2[i][t] = (t ? pc2[i][t - 1] : 0) + (time2reg[t] == r ? 1 : 0);
		}
	}

	Fenw fenw(n);

	forn(_, Q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;

		if(inv_reg[r1] < S) {
			cout << pc[inv_reg[r1]][r2] << endl;
		} else if (inv_reg[r2] < S) {
			int sum = 0, i2 = inv_reg[r2];
			for(int node: r2es[r1]) {
				int l = tin[node], r = tout[node];
				sum += pc2[i2][r] - (l ? pc2[i2][l - 1] : 0);
			}
			cout << sum << endl;
		} else {
			int sum = 0;
			for(int node: r2es[r1]) {
				int l = tin[node], r = tout[node];
				fenw.update(l, r, 1);
			}
			for(int node: r2es[r2]) {
				sum += fenw.at(tin[node]);
			}
			cout << sum << endl;
			for(int node: r2es[r1]) {
				int l = tin[node], r = tout[node];
				fenw.update(l, r, -1);
			}
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("haybales.in", "r", stdin);
//	freopen("haybales.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10440 KB	Output is correct
2	Correct	8 ms	10568 KB	Output is correct
3	Correct	8 ms	10696 KB	Output is correct
4	Correct	11 ms	10824 KB	Output is correct
5	Correct	12 ms	11080 KB	Output is correct
6	Correct	25 ms	12104 KB	Output is correct
7	Correct	35 ms	12232 KB	Output is correct
8	Correct	45 ms	12488 KB	Output is correct
9	Correct	72 ms	14152 KB	Output is correct
10	Correct	89 ms	16200 KB	Output is correct
11	Correct	140 ms	18376 KB	Output is correct
12	Correct	180 ms	20808 KB	Output is correct
13	Correct	209 ms	21960 KB	Output is correct
14	Correct	191 ms	24904 KB	Output is correct
15	Correct	181 ms	31424 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	887 ms	45460 KB	Output is correct
2	Correct	1062 ms	46248 KB	Output is correct
3	Correct	2192 ms	53056 KB	Output is correct
4	Correct	150 ms	26484 KB	Output is correct
5	Correct	452 ms	31292 KB	Output is correct
6	Correct	653 ms	37520 KB	Output is correct
7	Correct	943 ms	46696 KB	Output is correct
8	Correct	934 ms	63384 KB	Output is correct
9	Correct	2295 ms	85080 KB	Output is correct
10	Correct	2789 ms	101800 KB	Output is correct
11	Correct	6587 ms	107932 KB	Output is correct
12	Correct	1495 ms	102528 KB	Output is correct
13	Correct	2403 ms	102708 KB	Output is correct
14	Correct	2270 ms	107544 KB	Output is correct
15	Correct	3811 ms	113708 KB	Output is correct
16	Correct	3567 ms	119236 KB	Output is correct
17	Correct	3632 ms	116060 KB	Output is correct