oj.uz

Submission #478032

# Submission time Handle Problem Language Result Execution time Memory
478032 2021-10-05T06:43:41 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 8000 ms 35392 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];
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 10440 KB Output is correct
2 Correct 6 ms 10440 KB Output is correct
3 Correct 8 ms 10440 KB Output is correct
4 Correct 12 ms 10440 KB Output is correct
5 Correct 14 ms 10440 KB Output is correct
6 Correct 16 ms 10568 KB Output is correct
7 Correct 43 ms 10528 KB Output is correct
8 Correct 39 ms 10568 KB Output is correct
9 Correct 65 ms 10952 KB Output is correct
10 Correct 88 ms 11016 KB Output is correct
11 Correct 123 ms 11208 KB Output is correct
12 Correct 159 ms 11720 KB Output is correct
13 Correct 221 ms 11336 KB Output is correct
14 Correct 274 ms 11976 KB Output is correct
15 Correct 348 ms 14456 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2237 ms 15028 KB Output isn't correct
2 Incorrect 2746 ms 13792 KB Output isn't correct
3 Incorrect 3266 ms 16848 KB Output isn't correct
4 Correct 310 ms 12012 KB Output is correct
5 Correct 367 ms 13536 KB Output is correct
6 Execution timed out 8063 ms 16448 KB Time limit exceeded
7 Incorrect 5826 ms 15448 KB Output isn't correct
8 Execution timed out 8047 ms 26932 KB Time limit exceeded
9 Correct 2770 ms 19268 KB Output is correct
10 Execution timed out 8019 ms 35392 KB Time limit exceeded
11 Correct 5942 ms 18988 KB Output is correct
12 Execution timed out 8015 ms 20928 KB Time limit exceeded
13 Execution timed out 8016 ms 21088 KB Time limit exceeded
14 Execution timed out 8044 ms 24000 KB Time limit exceeded
15 Execution timed out 8042 ms 25056 KB Time limit exceeded
16 Execution timed out 8039 ms 30504 KB Time limit exceeded
17 Execution timed out 8032 ms 32704 KB Time limit exceeded