oj.uz

Submission #531798

# Submission time Handle Problem Language Result Execution time Memory
531798 2022-03-01T14:20:53 Z akhan42 Regions (IOI09_regions) C++17
25 / 100
 8000 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 && false) {
			cout << pc[inv_reg[r1]][r2] << endl;
		} else if (inv_reg[r2] < S && false) {
			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 7 ms 10696 KB Output is correct
4 Correct 11 ms 10824 KB Output is correct
5 Correct 16 ms 11140 KB Output is correct
6 Correct 22 ms 14332 KB Output is correct
7 Correct 33 ms 13224 KB Output is correct
8 Correct 36 ms 14536 KB Output is correct
9 Correct 63 ms 20480 KB Output is correct
10 Correct 70 ms 32712 KB Output is correct
11 Correct 172 ms 30272 KB Output is correct
12 Correct 211 ms 52672 KB Output is correct
13 Correct 216 ms 47412 KB Output is correct
14 Correct 388 ms 37692 KB Output is correct
15 Correct 458 ms 54848 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8090 ms 75888 KB Time limit exceeded
2 Execution timed out 8083 ms 85180 KB Time limit exceeded
3 Execution timed out 8080 ms 111280 KB Time limit exceeded
4 Correct 527 ms 84024 KB Output is correct
5 Correct 768 ms 101312 KB Output is correct
6 Runtime error 338 ms 131076 KB Execution killed with signal 9
7 Runtime error 501 ms 131072 KB Execution killed with signal 9
8 Runtime error 629 ms 131076 KB Execution killed with signal 9
9 Runtime error 1037 ms 131076 KB Execution killed with signal 9
10 Runtime error 1095 ms 131076 KB Execution killed with signal 9
11 Runtime error 1470 ms 131076 KB Execution killed with signal 9
12 Runtime error 1217 ms 131076 KB Execution killed with signal 9
13 Runtime error 1319 ms 131076 KB Execution killed with signal 9
14 Runtime error 1299 ms 131076 KB Execution killed with signal 9
15 Runtime error 1206 ms 131076 KB Execution killed with signal 9
16 Runtime error 1183 ms 131076 KB Execution killed with signal 9
17 Runtime error 1116 ms 131076 KB Execution killed with signal 9