oj.uz

Submission #531799

# Submission time Handle Problem Language Result Execution time Memory
531799 2022-03-01T14:21:05 Z akhan42 Regions (IOI09_regions) C++17
40 / 100
 1375 ms 131076 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 = 500;


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 6 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 14 ms 11080 KB Output is correct
6 Correct 30 ms 14280 KB Output is correct
7 Correct 35 ms 13128 KB Output is correct
8 Correct 39 ms 14540 KB Output is correct
9 Correct 56 ms 20540 KB Output is correct
10 Correct 89 ms 32696 KB Output is correct
11 Correct 96 ms 30292 KB Output is correct
12 Correct 158 ms 52672 KB Output is correct
13 Correct 142 ms 47420 KB Output is correct
14 Correct 184 ms 37792 KB Output is correct
15 Correct 231 ms 54800 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 76028 KB Output is correct
2 Correct 845 ms 85080 KB Output is correct
3 Correct 1375 ms 111232 KB Output is correct
4 Correct 392 ms 84028 KB Output is correct
5 Correct 575 ms 101328 KB Output is correct
6 Runtime error 330 ms 131076 KB Execution killed with signal 9
7 Runtime error 477 ms 131076 KB Execution killed with signal 9
8 Runtime error 617 ms 131076 KB Execution killed with signal 9
9 Runtime error 954 ms 131076 KB Execution killed with signal 9
10 Runtime error 1111 ms 131076 KB Execution killed with signal 9
11 Runtime error 1276 ms 131076 KB Execution killed with signal 9
12 Runtime error 1276 ms 131076 KB Execution killed with signal 9
13 Runtime error 1222 ms 131076 KB Execution killed with signal 9
14 Runtime error 1261 ms 131076 KB Execution killed with signal 9
15 Runtime error 1328 ms 131076 KB Execution killed with signal 9
16 Runtime error 1328 ms 131076 KB Execution killed with signal 9
17 Runtime error 1353 ms 131076 KB Execution killed with signal 9