제출 #909489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909489		IBory	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	431 ms	75992 KiB

long_mansion

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 500005;
int C[MAX], L[MAX], R[MAX];
pii E[MAX];
vector<int> K[MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N;
	for (int i = 1; i < N; ++i) cin >> C[i];
	for (int i = 1; i <= N; ++i) {
		int M;
		cin >> M;
		K[i].resize(M);
		for (int& n : K[i]) cin >> n;
	}

	vector<int> in(N + 1);
	for (int i = 1; i < N; ++i) {
		for (int k : K[i]) in[k] = i;
		L[i] = in[C[i]];
	}
	fill(in.begin(), in.end(), N + 1);
	for (int i = N - 1; i > 0; --i) {
		for (int k : K[i + 1]) in[k] = i + 1;
		R[i] = in[C[i]];
	}
	R[0] = R[N] = N + 1, L[0] = L[N] = 0;

	set<int, greater<int>> UD;
	set<pii> CR;
	for (int i = 1; i <= N; ++i) UD.insert(i);
	CR.emplace(0, R[0]);

	for (int i = 1; i <= N; ++i) {
		auto it = UD.lower_bound(i);
		while (it != UD.end()) {
			int cur = *it;
			if (cur <= L[i]) break;

			auto it2 = CR.lower_bound(pii{cur, 0}); it2--;
			while ((*it2).second <= i) it2 = CR.erase(it2), it2--;
			if ((*it2).first < L[i]) break;

			E[cur] = {(*it2).first + 1, i};
			it = UD.erase(it);
		}

		CR.emplace(i, R[i]);
	}

	cin >> Q;
	while (Q--) {
		int x, y;
		cin >> x >> y;
		bool can = E[x].first <= y && y <= E[x].second;
		cout << (can ? "YES" : "NO") << '\n';
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75