oj.uz

Submission #478184

# Submission time Handle Problem Language Result Execution time Memory
478184 2021-10-06T09:03:28 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
24 / 100
 3530 ms 64448 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 = 200;
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][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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11208 KB Output is correct
2 Correct 8 ms 11300 KB Output is correct
3 Correct 9 ms 11208 KB Output is correct
4 Correct 14 ms 11208 KB Output is correct
5 Correct 17 ms 11208 KB Output is correct
6 Correct 28 ms 11336 KB Output is correct
7 Correct 44 ms 11336 KB Output is correct
8 Correct 38 ms 11336 KB Output is correct
9 Correct 58 ms 11728 KB Output is correct
10 Correct 66 ms 11756 KB Output is correct
11 Correct 150 ms 12076 KB Output is correct
12 Correct 184 ms 12540 KB Output is correct
13 Correct 210 ms 12224 KB Output is correct
14 Correct 329 ms 12744 KB Output is correct
15 Incorrect 291 ms 15296 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1670 ms 16300 KB Output isn't correct
2 Incorrect 1245 ms 15552 KB Output isn't correct
3 Incorrect 3008 ms 17612 KB Output isn't correct
4 Correct 334 ms 12736 KB Output is correct
5 Correct 394 ms 14412 KB Output is correct
6 Incorrect 735 ms 17216 KB Output isn't correct
7 Incorrect 1447 ms 19132 KB Output isn't correct
8 Incorrect 1683 ms 28108 KB Output isn't correct
9 Incorrect 2641 ms 31040 KB Output isn't correct
10 Runtime error 200 ms 51900 KB Execution killed with signal 11
11 Runtime error 179 ms 41472 KB Execution killed with signal 11
12 Runtime error 197 ms 44912 KB Execution killed with signal 11
13 Runtime error 213 ms 45248 KB Execution killed with signal 11
14 Incorrect 2740 ms 24588 KB Output isn't correct
15 Incorrect 3492 ms 25816 KB Output isn't correct
16 Runtime error 199 ms 64448 KB Execution killed with signal 11
17 Incorrect 3530 ms 32604 KB Output isn't correct