oj.uz

답안 #477613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477613 2021-10-02T20:08:09 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
35 / 100
 8000 ms 33828 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 <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);
		}
	}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10440 KB Output is correct
2 Correct 8 ms 10440 KB Output is correct
3 Correct 7 ms 10476 KB Output is correct
4 Correct 10 ms 10440 KB Output is correct
5 Correct 10 ms 10440 KB Output is correct
6 Correct 24 ms 10568 KB Output is correct
7 Correct 21 ms 10568 KB Output is correct
8 Correct 50 ms 10568 KB Output is correct
9 Correct 67 ms 10996 KB Output is correct
10 Correct 112 ms 10952 KB Output is correct
11 Correct 159 ms 11224 KB Output is correct
12 Correct 190 ms 11720 KB Output is correct
13 Correct 188 ms 11328 KB Output is correct
14 Correct 336 ms 11972 KB Output is correct
15 Correct 277 ms 14508 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2481 ms 15028 KB Output isn't correct
2 Incorrect 3022 ms 13868 KB Output isn't correct
3 Incorrect 3498 ms 16844 KB Output isn't correct
4 Correct 296 ms 11968 KB Output is correct
5 Correct 418 ms 13632 KB Output is correct
6 Execution timed out 8013 ms 14784 KB Time limit exceeded
7 Execution timed out 8003 ms 15256 KB Time limit exceeded
8 Execution timed out 8070 ms 22976 KB Time limit exceeded
9 Correct 2926 ms 19212 KB Output is correct
10 Execution timed out 8055 ms 33828 KB Time limit exceeded
11 Correct 4641 ms 18968 KB Output is correct
12 Execution timed out 8036 ms 20800 KB Time limit exceeded
13 Execution timed out 8032 ms 20972 KB Time limit exceeded
14 Execution timed out 8055 ms 22240 KB Time limit exceeded
15 Execution timed out 8005 ms 24768 KB Time limit exceeded
16 Execution timed out 8105 ms 30376 KB Time limit exceeded
17 Execution timed out 8021 ms 30784 KB Time limit exceeded