oj.uz

답안 #539001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539001 2022-03-18T07:46:07 Z valerikk Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1033 ms 70824 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500500;

int n;
int c[N];
int b[N];
vector<int> a[N];
vector<int> inds[N];
int L[N], R[N];
int cnt[N];

bool check(int l, int r, int x) {
	auto it = lower_bound(inds[x].begin(), inds[x].end(), l);
	return it != inds[x].end() && *it <= r;
}

void rec(int l, int r) {
	if (l > r) {
		return;
	}

	int m = (l + r) / 2;
	rec(l, m - 1);
	rec(m + 1, r);

	vector<int> left;
	for (int i = m - 1; i >= l; --i) {
		if (R[i] == m - 1 && check(L[i], R[i], c[m - 1])) {
			left.push_back(i);
		}
	}

	vector<int> right;
	for (int i = m + 1; i <= r; ++i) {
		if (L[i] == m + 1 && check(L[i], R[i], c[m])) {
			right.push_back(i);
		}
	}

	vector<int> clr;
	
	auto add = [&](int i) {
		for (int x : a[i]) {
			++cnt[x];
			clr.push_back(x);
		}
	};

	auto clear = [&]() {
		for (int x : clr) {
			cnt[x] = 0;
		}
	};

	int tl = m, tr = m;
		
	auto go = [&]() {
		while (true) {
			if (tl > l && cnt[c[tl - 1]] > 0) {
				--tl;
				add(tl);
			} else if (tr < r && cnt[c[tr]] > 0) {
				++tr;
				add(tr);
			} else {
				break;
			}
		}
	};

	add(m);
	go();
	
	L[m] = tl;
	R[m] = tr;

	int last = m;
	for (int i : left) {
		for (int j = last - 1; j >= L[i]; --j) {
			add(j);
		}
		go();
		L[i] = tl;
		R[i] = tr;
		last = L[i];
	}

	clear();

	tl = m, tr = m;
	add(m);
	go();

	last = m;
	for (int i : right) {
		for (int j = last + 1; j <= R[i]; ++j) {
			add(j);
		}
		go();
		L[i] = tl;
		R[i] = tr;
		last = R[i];
	}

	clear();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		cin >> c[i];
		--c[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
		for (int j = 0; j < b[i]; ++j) {
			int x;
			cin >> x;
			--x;
			a[i].push_back(x);
			inds[x].push_back(i);
		}
	}

	rec(0, n - 1);

	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		cout << (y >= L[x] && y <= R[x] ? "YES" : "NO") << "\n";
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 24148 KB Output is correct
2 Correct 17 ms 24148 KB Output is correct
3 Correct 20 ms 24276 KB Output is correct
4 Correct 16 ms 24020 KB Output is correct
5 Correct 19 ms 24104 KB Output is correct
6 Correct 16 ms 24108 KB Output is correct
7 Correct 15 ms 24116 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 24148 KB Output is correct
2 Correct 17 ms 24148 KB Output is correct
3 Correct 20 ms 24276 KB Output is correct
4 Correct 16 ms 24020 KB Output is correct
5 Correct 19 ms 24104 KB Output is correct
6 Correct 16 ms 24108 KB Output is correct
7 Correct 15 ms 24116 KB Output is correct
8 Correct 114 ms 29936 KB Output is correct
9 Correct 110 ms 29972 KB Output is correct
10 Correct 114 ms 30284 KB Output is correct
11 Correct 111 ms 30688 KB Output is correct
12 Correct 104 ms 29552 KB Output is correct
13 Correct 110 ms 30100 KB Output is correct
14 Correct 109 ms 30104 KB Output is correct
15 Correct 106 ms 30128 KB Output is correct
16 Correct 106 ms 29896 KB Output is correct
17 Correct 103 ms 30076 KB Output is correct
18 Correct 103 ms 30148 KB Output is correct
19 Correct 103 ms 30124 KB Output is correct
20 Correct 104 ms 30152 KB Output is correct
21 Correct 109 ms 30068 KB Output is correct
22 Correct 104 ms 29956 KB Output is correct
23 Correct 109 ms 29852 KB Output is correct
24 Correct 110 ms 29900 KB Output is correct
25 Correct 115 ms 29944 KB Output is correct
26 Correct 110 ms 29920 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 409 ms 45512 KB Output is correct
2 Correct 412 ms 45024 KB Output is correct
3 Correct 404 ms 44580 KB Output is correct
4 Correct 407 ms 45304 KB Output is correct
5 Correct 401 ms 45284 KB Output is correct
6 Correct 302 ms 40032 KB Output is correct
7 Correct 322 ms 38228 KB Output is correct
8 Correct 325 ms 41988 KB Output is correct
9 Correct 355 ms 38220 KB Output is correct
10 Correct 363 ms 38156 KB Output is correct
11 Correct 357 ms 41972 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 24148 KB Output is correct
2 Correct 17 ms 24148 KB Output is correct
3 Correct 20 ms 24276 KB Output is correct
4 Correct 16 ms 24020 KB Output is correct
5 Correct 19 ms 24104 KB Output is correct
6 Correct 16 ms 24108 KB Output is correct
7 Correct 15 ms 24116 KB Output is correct
8 Correct 114 ms 29936 KB Output is correct
9 Correct 110 ms 29972 KB Output is correct
10 Correct 114 ms 30284 KB Output is correct
11 Correct 111 ms 30688 KB Output is correct
12 Correct 104 ms 29552 KB Output is correct
13 Correct 110 ms 30100 KB Output is correct
14 Correct 109 ms 30104 KB Output is correct
15 Correct 106 ms 30128 KB Output is correct
16 Correct 106 ms 29896 KB Output is correct
17 Correct 103 ms 30076 KB Output is correct
18 Correct 103 ms 30148 KB Output is correct
19 Correct 103 ms 30124 KB Output is correct
20 Correct 104 ms 30152 KB Output is correct
21 Correct 109 ms 30068 KB Output is correct
22 Correct 104 ms 29956 KB Output is correct
23 Correct 109 ms 29852 KB Output is correct
24 Correct 110 ms 29900 KB Output is correct
25 Correct 115 ms 29944 KB Output is correct
26 Correct 110 ms 29920 KB Output is correct
27 Correct 409 ms 45512 KB Output is correct
28 Correct 412 ms 45024 KB Output is correct
29 Correct 404 ms 44580 KB Output is correct
30 Correct 407 ms 45304 KB Output is correct
31 Correct 401 ms 45284 KB Output is correct
32 Correct 302 ms 40032 KB Output is correct
33 Correct 322 ms 38228 KB Output is correct
34 Correct 325 ms 41988 KB Output is correct
35 Correct 355 ms 38220 KB Output is correct
36 Correct 363 ms 38156 KB Output is correct
37 Correct 357 ms 41972 KB Output is correct
38 Correct 412 ms 58972 KB Output is correct
39 Correct 404 ms 62944 KB Output is correct
40 Correct 367 ms 53000 KB Output is correct
41 Correct 1033 ms 70052 KB Output is correct
42 Correct 241 ms 39444 KB Output is correct
43 Correct 257 ms 39244 KB Output is correct
44 Correct 481 ms 48844 KB Output is correct
45 Correct 455 ms 49308 KB Output is correct
46 Correct 459 ms 49868 KB Output is correct
47 Correct 343 ms 39876 KB Output is correct
48 Correct 320 ms 39272 KB Output is correct
49 Correct 565 ms 48140 KB Output is correct
50 Correct 617 ms 48908 KB Output is correct
51 Correct 618 ms 50560 KB Output is correct
52 Correct 292 ms 50976 KB Output is correct
53 Correct 367 ms 62432 KB Output is correct
54 Correct 374 ms 70824 KB Output is correct
55 Correct 321 ms 60820 KB Output is correct