oj.uz

답안 #531801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531801 2022-03-01T14:23:45 Z akhan42 Regions (IOI09_regions) C++17
100 / 100
 6587 ms 119236 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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