oj.uz

Submission #477612

# Submission time Handle Problem Language Result Execution time Memory
477612 2021-10-02T19:52:30 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 8000 ms 33860 KB 
#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 <int>> 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);
		}
	}
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		int 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 5 ms 10440 KB Output is correct
2 Correct 6 ms 10440 KB Output is correct
3 Correct 8 ms 10428 KB Output is correct
4 Correct 9 ms 10440 KB Output is correct
5 Correct 13 ms 10440 KB Output is correct
6 Correct 23 ms 10568 KB Output is correct
7 Correct 31 ms 10568 KB Output is correct
8 Correct 45 ms 10568 KB Output is correct
9 Correct 69 ms 10904 KB Output is correct
10 Correct 109 ms 10976 KB Output is correct
11 Correct 164 ms 11336 KB Output is correct
12 Correct 97 ms 11720 KB Output is correct
13 Correct 216 ms 11464 KB Output is correct
14 Correct 303 ms 11932 KB Output is correct
15 Correct 195 ms 14556 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2270 ms 15036 KB Output isn't correct
2 Incorrect 2750 ms 13872 KB Output isn't correct
3 Incorrect 2916 ms 16844 KB Output isn't correct
4 Correct 295 ms 11976 KB Output is correct
5 Correct 395 ms 13640 KB Output is correct
6 Execution timed out 8015 ms 14784 KB Time limit exceeded
7 Execution timed out 8061 ms 15252 KB Time limit exceeded
8 Execution timed out 8069 ms 22952 KB Time limit exceeded
9 Correct 2444 ms 19192 KB Output is correct
10 Execution timed out 8085 ms 33860 KB Time limit exceeded
11 Correct 4188 ms 18988 KB Output is correct
12 Execution timed out 8095 ms 20716 KB Time limit exceeded
13 Execution timed out 8074 ms 20880 KB Time limit exceeded
14 Execution timed out 8064 ms 22188 KB Time limit exceeded
15 Execution timed out 8087 ms 24832 KB Time limit exceeded
16 Execution timed out 8092 ms 30372 KB Time limit exceeded
17 Execution timed out 8090 ms 30784 KB Time limit exceeded