oj.uz

Submission #478179

# Submission time Handle Problem Language Result Execution time Memory
478179 2021-10-06T08:22:12 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 5365 ms 34804 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 = 447;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], timer=1, stwho[MX];
long long prep[B+10][MX];

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;
	int index[R+1], cur=0;
	for(int i=1; i<=R; ++i) if(region[i].size()>B) {
		bigs.push_back(i);
		index[i] = cur++;
	}
	FenwickTree A; 
	for(int all=1; all<=R; ++all) {
		for(auto it : region[all]) {
			A.add(st[it], 1);
		}
		for(auto b : bigs) {
			for(auto it : region[index[b]]) {
				prep[index[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[index[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 7 ms 10440 KB Output is correct
2 Correct 10 ms 10440 KB Output is correct
3 Correct 8 ms 10440 KB Output is correct
4 Correct 13 ms 10440 KB Output is correct
5 Correct 18 ms 10452 KB Output is correct
6 Correct 29 ms 10568 KB Output is correct
7 Correct 47 ms 10568 KB Output is correct
8 Correct 47 ms 10592 KB Output is correct
9 Correct 64 ms 10940 KB Output is correct
10 Correct 113 ms 10996 KB Output is correct
11 Correct 169 ms 11336 KB Output is correct
12 Correct 156 ms 11716 KB Output is correct
13 Correct 233 ms 11404 KB Output is correct
14 Correct 313 ms 12024 KB Output is correct
15 Correct 330 ms 14528 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2236 ms 15160 KB Output isn't correct
2 Incorrect 2502 ms 13960 KB Output isn't correct
3 Incorrect 3346 ms 16884 KB Output isn't correct
4 Correct 414 ms 11992 KB Output is correct
5 Correct 509 ms 13628 KB Output is correct
6 Incorrect 728 ms 16660 KB Output isn't correct
7 Incorrect 1629 ms 15564 KB Output isn't correct
8 Incorrect 1701 ms 27624 KB Output isn't correct
9 Correct 2930 ms 19224 KB Output is correct
10 Incorrect 4239 ms 34804 KB Output isn't correct
11 Correct 5365 ms 18972 KB Output is correct
12 Incorrect 1512 ms 20792 KB Output isn't correct
13 Incorrect 2064 ms 20988 KB Output isn't correct
14 Incorrect 2710 ms 23860 KB Output isn't correct
15 Incorrect 3787 ms 25004 KB Output isn't correct
16 Incorrect 3235 ms 30340 KB Output isn't correct
17 Incorrect 3420 ms 31756 KB Output isn't correct