oj.uz

Submission #477615

# Submission time Handle Problem Language Result Execution time Memory
477615 2021-10-02T20:38:06 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 8000 ms 43816 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n = MX;

    int sum(int r) {
    	if(bit.empty()) bit.resize(n);
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
    	if(bit.empty()) bit.resize(n);
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
const int B = 400;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], timer=1, stwho[MX];
map <int, vector <long long>> prep;
void Flat(int v, int p) {
	stwho[timer] = v;
	st[v] = timer++;
	region[H[v]].push_back(st[v]);
	for(auto to : g[v]) if(to!=p) {
		Flat(to, v);
	}
	en[v] = timer-1;
}
int main() {
	cin >> N >> R >> Q;
	cin >> H[1];
	for(int i=2; i<=N; ++i) {
		int p; cin >> p >> H[i];
		g[p].push_back(i);
	}
	Flat(1, 1);
	vector <int> bigs;
	for(int i=1; i<=R; ++i) if(region[i].size()>B) {
		bigs.push_back(i);
	}
	FenwickTree A; 
	for(int all=1; all<=R; ++all) {
		for(auto it : region[all]) {
			A.add(st[it], 1);
		}
		for(auto b : bigs) {
			if(prep[b].empty()) prep[b].resize(R+1);
			for(auto it : region[b]) {
				prep[b][all] += A.sum(st[it], en[it]);
			}
		}
		for(auto it : region[all]) {
			A.add(st[it], -1);
		}
	}

	// O(Q(rootNlogN + logR))
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		long long ans = 0;
		if(region[r1].size()>B) {
			ans = prep[r1][r2];
		} else {
			for(auto p1 : region[r1]) {
				auto it = upper_bound(region[r2].begin(), region[r2].end(), en[stwho[p1]]);
				auto it2 = lower_bound(region[r2].begin(), region[r2].end(), p1);
				ans += it-it2; 
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10416 KB Output is correct
2 Correct 6 ms 10440 KB Output is correct
3 Correct 9 ms 10496 KB Output is correct
4 Correct 10 ms 10440 KB Output is correct
5 Correct 15 ms 10440 KB Output is correct
6 Correct 31 ms 10568 KB Output is correct
7 Correct 40 ms 10568 KB Output is correct
8 Correct 38 ms 10568 KB Output is correct
9 Correct 62 ms 10952 KB Output is correct
10 Correct 56 ms 11016 KB Output is correct
11 Correct 115 ms 11336 KB Output is correct
12 Correct 157 ms 11712 KB Output is correct
13 Correct 238 ms 11336 KB Output is correct
14 Correct 328 ms 12040 KB Output is correct
15 Correct 332 ms 14552 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2264 ms 15036 KB Output isn't correct
2 Incorrect 2792 ms 13876 KB Output isn't correct
3 Incorrect 3682 ms 16840 KB Output isn't correct
4 Correct 340 ms 11976 KB Output is correct
5 Correct 367 ms 13632 KB Output is correct
6 Execution timed out 8053 ms 16448 KB Time limit exceeded
7 Execution timed out 8013 ms 16304 KB Time limit exceeded
8 Execution timed out 8048 ms 26908 KB Time limit exceeded
9 Correct 2750 ms 19264 KB Output is correct
10 Execution timed out 8045 ms 43816 KB Time limit exceeded
11 Correct 4761 ms 18992 KB Output is correct
12 Execution timed out 8101 ms 20928 KB Time limit exceeded
13 Execution timed out 8023 ms 21032 KB Time limit exceeded
14 Execution timed out 8042 ms 24104 KB Time limit exceeded
15 Execution timed out 8016 ms 25108 KB Time limit exceeded
16 Execution timed out 8036 ms 30528 KB Time limit exceeded
17 Execution timed out 8028 ms 32708 KB Time limit exceeded