oj.uz

Submission #531790

# Submission time Handle Problem Language Result Execution time Memory
531790 2022-03-01T14:05:00 Z akhan42 Regions (IOI09_regions) C++17
30 / 100
 1208 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];


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;
	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(node, n) {
			pc2[i][node] = (node ? pc2[i][node - 1] : 0) + (e2r[node] == 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 10680 KB Output is correct
4 Correct 8 ms 10904 KB Output is correct
5 Correct 9 ms 11080 KB Output is correct
6 Correct 28 ms 14280 KB Output is correct
7 Correct 34 ms 13128 KB Output is correct
8 Correct 33 ms 14536 KB Output is correct
9 Correct 49 ms 20424 KB Output is correct
10 Correct 97 ms 32700 KB Output is correct
11 Correct 110 ms 30248 KB Output is correct
12 Correct 122 ms 52504 KB Output is correct
13 Correct 156 ms 47424 KB Output is correct
14 Correct 175 ms 37568 KB Output is correct
15 Correct 203 ms 54692 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 75584 KB Output is correct
2 Correct 895 ms 84860 KB Output is correct
3 Correct 1081 ms 110932 KB Output is correct
4 Incorrect 375 ms 83904 KB Output isn't correct
5 Incorrect 512 ms 101180 KB Output isn't correct
6 Runtime error 309 ms 131076 KB Execution killed with signal 9
7 Runtime error 426 ms 131076 KB Execution killed with signal 9
8 Runtime error 535 ms 131076 KB Execution killed with signal 9
9 Runtime error 890 ms 131076 KB Execution killed with signal 9
10 Runtime error 977 ms 131076 KB Execution killed with signal 9
11 Runtime error 1208 ms 131076 KB Execution killed with signal 9
12 Runtime error 1089 ms 131076 KB Execution killed with signal 9
13 Runtime error 1128 ms 131076 KB Execution killed with signal 9
14 Runtime error 1129 ms 131076 KB Execution killed with signal 9
15 Runtime error 1171 ms 131076 KB Execution killed with signal 9
16 Runtime error 1157 ms 131076 KB Execution killed with signal 9
17 Runtime error 1114 ms 131076 KB Execution killed with signal 9