Submission #1097587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097587		peti1234	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	755 ms	47696 KiB

long_mansion

// Source: https://usaco.guide/general/io

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

const int c=500005;

int n, q, t[c], ord[c], l[c], r[c], el[c], kov[c];
vector<int> sor[c];

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i=1; i<n; i++) {
		cin >> t[i];
	}
	for (int i=1; i<=n; i++) {
		int x;
		cin >> x;
		while (x--) {
			int y;
			cin >> y;
			sor[y].push_back(i);
		}
	}

	for (int i=1; i<n; i++) {
		int si=sor[t[i]].size();
		int lo=-1, hi=si, mid;
		while (hi-lo>1) {
			mid=(hi+lo)/2;
			if (sor[t[i]][mid]<=i) {
				lo=mid;
			} else {
				hi=mid;
			}
		}
		if (lo==-1) {
			el[i]=0;
		} else {
			el[i]=sor[t[i]][lo];
		}
		if (hi==si) {
			kov[i]=n+1;
		} else {
			kov[i]=sor[t[i]][hi];
		}

		//cout << i << " " << el[i] << " " << kov[i] << "\n";
	}
	//return 0;

	for (int i=1; i<=n; i++) {
		ord[i]=i;
	}
	random_shuffle(ord+1, ord+n+1);
	for (int i=1; i<=n; i++) {
		int bal=ord[i], jobb=ord[i];
		while (true) {
			int d=jobb-bal;
			if (l[bal]) {
				jobb=max(jobb, r[bal]);
				bal=min(bal, l[bal]);
			}
			if (r[jobb]) {
				bal=min(bal, l[jobb]);
				jobb=max(jobb, r[jobb]);
			}
			if (bal>1 && kov[bal-1]<=jobb) {
				bal--;
			}
			if (jobb<n && el[jobb]>=bal) {
				jobb++;
			}
			if (jobb-bal==d) {
				break;
			}
		}
		l[ord[i]]=bal, r[ord[i]]=jobb;
	}

	/*for (int i=1; i<=n; i++) {
		cout << i << " " << l[i] << " " << r[i] << "\n";
	}*/

	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << (l[a]<=b && b<=r[a] ? "YES" : "NO") << "\n";
	}
}

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