Submission #538073

#	Time	Username	Problem	Language	Result	Execution time	Memory
538073		fhvirus	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	279 ms	43384 KiB

long_mansion

// jiaqiyang orz
// solution adapted from his/her submission
#include<bits/stdc++.h>
using namespace std;

const int kN = 500005;
int N, Q, C[kN], B[kN];
vector<int> A[kN];

int prv[kN], nxt[kN], occ[kN];
int lb[kN], rb[kN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i < N; ++i)
		cin >> C[i];
	for (int i = 1; i <= N; ++i) {
		cin >> B[i];
		A[i].resize(B[i]);
		for (int& a: A[i])
			cin >> a;
	}

	for (int i = 1; i < N; ++i) {
		for (const int& a: A[i])
			occ[a] = i;
		prv[i] = occ[C[i]];
	}
	for (int i = 1; i <= N; ++i)
		occ[i] = N + 1;
	for (int i = N - 1; i >= 1; --i) {
		for (const int& a: A[i + 1])
			occ[a] = i + 1;
		nxt[i] = occ[C[i]];
	}

	for (int i = 1; i <= N; ++i) {
		int l = i, r = i;
		while (true) {
			if (l > 1 and l <= nxt[l - 1] and nxt[l - 1] <= r) {
				r = max(r, rb[l - 1]);
				l = min(l, lb[l - 1]);
			} else if (r < N and l <= prv[r] and prv[r] <= r) {
				++r;
			} else break;
		}
		lb[i] = l; rb[i] = r;
	}

	cin >> Q;
	for (int X, Y, i = 0; i < Q; ++i) {
		cin >> X >> Y;
		cout << (lb[X] <= Y and Y <= rb[X] ? "YES\n" : "NO\n");
	}
	
	return 0;
}

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