Submission #168263

#	Time	Username	Problem	Language	Result	Execution time	Memory
168263		iefnah06	Long Mansion (JOI17_long_mansion)	C++11	100 / 100	364 ms	43992 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5.1e5;
int N;
int C[MAXN];
vector<int> A[MAXN];

int last[MAXN];
int prv[MAXN]; // previous position with corresponding key
int nxt[MAXN]; // next

int lo[MAXN];
int hi[MAXN];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N-1; i++) {
		cin >> C[i];
	}
	for (int i = 1; i <= N; i++) {
		int B; cin >> B;
		A[i].reserve(B);
		for (int j = 0; j < B; j++) {
			int v; cin >> v;
			A[i].push_back(v);
		}
	}

	for (int i = 1; i <= N-1; i++) {
		for (int v : A[i]) {
			last[v] = i;
		}
		prv[i] = last[C[i]];
	}

	fill(last + 1, last + N + 1, N+1);
	for (int i = N; i >= 2; i--) {
		for (int v : A[i]) {
			last[v] = i;
		}
		nxt[i-1] = last[C[i-1]];
	}

	for (int i = 1; i <= N; i++) {
		int l = i;
		int r = i;
		while (true) {
			if (l > 1 && nxt[l-1] <= r) {
				r = max(r, hi[l-1]);
				l = lo[l-1];
				continue;
			}
			if (r+1 <= N && prv[r] >= l) {
				r++;
				continue;
			}
			break;
		}
		lo[i] = l;
		hi[i] = r;
	}

	int Q; cin >> Q;
	while (Q--) {
		int x, y; cin >> x >> y;
		if (lo[x] <= y && y <= hi[x]) {
			cout << "YES" << '\n';
		} else {
			cout << "NO" << '\n';
		}
	}

	return 0;
}

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