oj.uz

Submission #478180

# Submission time Handle Problem Language Result Execution time Memory
478180 2021-10-06T08:33:45 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 4746 ms 35592 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
struct FenwickTree {
    vector<long long> 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; 
			}
		}
		assert(ans>=0);
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11208 KB Output is correct
2 Correct 8 ms 11228 KB Output is correct
3 Correct 10 ms 11208 KB Output is correct
4 Correct 12 ms 11208 KB Output is correct
5 Correct 16 ms 11292 KB Output is correct
6 Correct 27 ms 11348 KB Output is correct
7 Correct 44 ms 11336 KB Output is correct
8 Correct 32 ms 11336 KB Output is correct
9 Correct 65 ms 11720 KB Output is correct
10 Correct 108 ms 11780 KB Output is correct
11 Correct 152 ms 12052 KB Output is correct
12 Correct 113 ms 12488 KB Output is correct
13 Correct 180 ms 12132 KB Output is correct
14 Correct 314 ms 12764 KB Output is correct
15 Correct 297 ms 15252 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1934 ms 16000 KB Output isn't correct
2 Incorrect 2246 ms 14660 KB Output isn't correct
3 Incorrect 3383 ms 17744 KB Output isn't correct
4 Correct 337 ms 12736 KB Output is correct
5 Correct 363 ms 14408 KB Output is correct
6 Incorrect 648 ms 17496 KB Output isn't correct
7 Incorrect 1844 ms 16164 KB Output isn't correct
8 Incorrect 1533 ms 28224 KB Output isn't correct
9 Correct 2766 ms 20032 KB Output is correct
10 Incorrect 4189 ms 35592 KB Output isn't correct
11 Correct 4746 ms 19716 KB Output is correct
12 Incorrect 1739 ms 21516 KB Output isn't correct
13 Incorrect 2270 ms 21788 KB Output isn't correct
14 Incorrect 2881 ms 24644 KB Output isn't correct
15 Incorrect 3595 ms 25784 KB Output isn't correct
16 Incorrect 3375 ms 31208 KB Output isn't correct
17 Incorrect 3614 ms 32556 KB Output isn't correct