oj.uz

Submission #478183

# Submission time Handle Problem Language Result Execution time Memory
478183 2021-10-06T09:01:22 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
10 / 100
 8000 ms 131076 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 = 50;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], timer=1, stwho[MX];
long long prep[5000][25001];

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
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11208 KB Output is correct
2 Correct 8 ms 11208 KB Output is correct
3 Correct 11 ms 11208 KB Output is correct
4 Correct 13 ms 11208 KB Output is correct
5 Correct 17 ms 11208 KB Output is correct
6 Correct 32 ms 11248 KB Output is correct
7 Correct 24 ms 11336 KB Output is correct
8 Correct 48 ms 11372 KB Output is correct
9 Correct 74 ms 11720 KB Output is correct
10 Correct 93 ms 11800 KB Output is correct
11 Incorrect 240 ms 13328 KB Output isn't correct
12 Incorrect 238 ms 13236 KB Output isn't correct
13 Incorrect 467 ms 14532 KB Output isn't correct
14 Incorrect 439 ms 13996 KB Output isn't correct
15 Incorrect 464 ms 16764 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1467 ms 17056 KB Output isn't correct
2 Incorrect 1305 ms 15652 KB Output isn't correct
3 Incorrect 2292 ms 19500 KB Output isn't correct
4 Incorrect 423 ms 15972 KB Output isn't correct
5 Incorrect 795 ms 19720 KB Output isn't correct
6 Incorrect 488 ms 17268 KB Output isn't correct
7 Incorrect 1315 ms 24604 KB Output isn't correct
8 Incorrect 2610 ms 52764 KB Output isn't correct
9 Incorrect 7293 ms 84376 KB Output isn't correct
10 Runtime error 3575 ms 131076 KB Execution killed with signal 9
11 Incorrect 6536 ms 123224 KB Output isn't correct
12 Incorrect 7536 ms 88972 KB Output isn't correct
13 Incorrect 6952 ms 89180 KB Output isn't correct
14 Execution timed out 8037 ms 90068 KB Time limit exceeded
15 Runtime error 6028 ms 131076 KB Execution killed with signal 9
16 Incorrect 7177 ms 128836 KB Output isn't correct
17 Execution timed out 8019 ms 99956 KB Time limit exceeded