oj.uz

Submission #477614

# Submission time Handle Problem Language Result Execution time Memory
477614 2021-10-02T20:34:32 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 8000 ms 43744 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);
			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 7 ms 10440 KB Output is correct
2 Correct 7 ms 10440 KB Output is correct
3 Correct 8 ms 10440 KB Output is correct
4 Correct 9 ms 10440 KB Output is correct
5 Correct 15 ms 10440 KB Output is correct
6 Correct 25 ms 10568 KB Output is correct
7 Correct 36 ms 10568 KB Output is correct
8 Correct 47 ms 10568 KB Output is correct
9 Correct 55 ms 10952 KB Output is correct
10 Correct 100 ms 10964 KB Output is correct
11 Correct 155 ms 11336 KB Output is correct
12 Correct 214 ms 11712 KB Output is correct
13 Correct 222 ms 11444 KB Output is correct
14 Correct 330 ms 11944 KB Output is correct
15 Correct 334 ms 14532 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 421 ms 15032 KB Execution killed with signal 13
2 Incorrect 2748 ms 13896 KB Output isn't correct
3 Runtime error 535 ms 16780 KB Execution killed with signal 13
4 Correct 352 ms 11968 KB Output is correct
5 Correct 398 ms 13632 KB Output is correct
6 Execution timed out 8038 ms 16416 KB Time limit exceeded
7 Execution timed out 8028 ms 16308 KB Time limit exceeded
8 Execution timed out 8093 ms 26904 KB Time limit exceeded
9 Correct 2703 ms 19184 KB Output is correct
10 Execution timed out 8076 ms 43744 KB Time limit exceeded
11 Correct 5537 ms 18868 KB Output is correct
12 Execution timed out 8080 ms 20856 KB Time limit exceeded
13 Execution timed out 8042 ms 21128 KB Time limit exceeded
14 Execution timed out 8066 ms 24088 KB Time limit exceeded
15 Execution timed out 8034 ms 25172 KB Time limit exceeded
16 Execution timed out 8029 ms 30576 KB Time limit exceeded
17 Execution timed out 8026 ms 32600 KB Time limit exceeded