oj.uz

Submission #531793

# Submission time Handle Problem Language Result Execution time Memory
531793 2022-03-01T14:11:56 Z akhan42 Regions (IOI09_regions) C++17
0 / 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, -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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 10440 KB Output isn't correct
2 Incorrect 6 ms 10568 KB Output isn't correct
3 Incorrect 8 ms 10696 KB Output isn't correct
4 Incorrect 13 ms 10824 KB Output isn't correct
5 Incorrect 14 ms 11084 KB Output isn't correct
6 Incorrect 30 ms 14280 KB Output isn't correct
7 Incorrect 41 ms 13128 KB Output isn't correct
8 Incorrect 45 ms 14536 KB Output isn't correct
9 Incorrect 55 ms 20468 KB Output isn't correct
10 Incorrect 119 ms 32724 KB Output isn't correct
11 Incorrect 158 ms 30352 KB Output isn't correct
12 Incorrect 194 ms 52660 KB Output isn't correct
13 Incorrect 266 ms 47508 KB Output isn't correct
14 Incorrect 379 ms 37700 KB Output isn't correct
15 Incorrect 382 ms 54848 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8009 ms 75900 KB Time limit exceeded
2 Execution timed out 8023 ms 85176 KB Time limit exceeded
3 Execution timed out 8036 ms 111448 KB Time limit exceeded
4 Incorrect 552 ms 84028 KB Output isn't correct
5 Incorrect 545 ms 101320 KB Output isn't correct
6 Runtime error 321 ms 131076 KB Execution killed with signal 9
7 Runtime error 416 ms 131076 KB Execution killed with signal 9
8 Runtime error 542 ms 131076 KB Execution killed with signal 9
9 Runtime error 840 ms 131076 KB Execution killed with signal 9
10 Runtime error 1006 ms 131076 KB Execution killed with signal 9
11 Runtime error 1231 ms 131076 KB Execution killed with signal 9
12 Runtime error 1101 ms 131076 KB Execution killed with signal 9
13 Runtime error 1077 ms 131076 KB Execution killed with signal 9
14 Runtime error 1111 ms 131076 KB Execution killed with signal 9
15 Runtime error 1134 ms 131076 KB Execution killed with signal 9
16 Runtime error 1128 ms 131076 KB Execution killed with signal 9
17 Runtime error 1058 ms 131076 KB Execution killed with signal 9