Submission #313764

#	Time	Username	Problem	Language	Result	Execution time	Memory
313764		VROOM_VARUN	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	317 ms	41720 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]];
	}
 
  	int cnt = 0;
  
	for (int i = 1; i <= N; i++) {
		int l = i;
		int r = i;
		while (true) {
            cnt++;
			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;
	}
  
  	if(cnt >= ((int)1e7)) {
      cout << "-1\n";
      exit(0);
    }
 
	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