oj.uz

Submission #531791

# Submission time Handle Problem Language Result Execution time Memory
531791 2022-03-01T14:10:11 Z akhan42 Regions (IOI09_regions) C++17
30 / 100
 3103 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, -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) {
			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 10 ms 10816 KB Output is correct
5 Correct 14 ms 11080 KB Output is correct
6 Correct 23 ms 14280 KB Output is correct
7 Correct 39 ms 13120 KB Output is correct
8 Correct 37 ms 14448 KB Output is correct
9 Correct 67 ms 20552 KB Output is correct
10 Correct 91 ms 32708 KB Output is correct
11 Correct 132 ms 30348 KB Output is correct
12 Correct 149 ms 52580 KB Output is correct
13 Correct 192 ms 47420 KB Output is correct
14 Correct 190 ms 37704 KB Output is correct
15 Correct 245 ms 54876 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1836 ms 75840 KB Output is correct
2 Correct 3103 ms 85184 KB Output is correct
3 Correct 2462 ms 111296 KB Output is correct
4 Incorrect 452 ms 84028 KB Output isn't correct
5 Incorrect 615 ms 101320 KB Output isn't correct
6 Runtime error 319 ms 131076 KB Execution killed with signal 9
7 Runtime error 446 ms 131076 KB Execution killed with signal 9
8 Runtime error 577 ms 131076 KB Execution killed with signal 9
9 Runtime error 1054 ms 131076 KB Execution killed with signal 9
10 Runtime error 1167 ms 131076 KB Execution killed with signal 9
11 Runtime error 1348 ms 131076 KB Execution killed with signal 9
12 Runtime error 1209 ms 131076 KB Execution killed with signal 9
13 Runtime error 1151 ms 131076 KB Execution killed with signal 9
14 Runtime error 1348 ms 131076 KB Execution killed with signal 9
15 Runtime error 1263 ms 131076 KB Execution killed with signal 9
16 Runtime error 1139 ms 131076 KB Execution killed with signal 9
17 Runtime error 1109 ms 131076 KB Execution killed with signal 9