Submission #294539

#	Time	Username	Problem	Language	Result	Execution time	Memory
294539		nandonathaniel	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	303 ms	52344 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;

int C[MAXN],kiri[MAXN],kanan[MAXN],nearL[MAXN],nearR[MAXN],last[MAXN];
vector<int> kunci[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,q,b,a;
	cin >> n;
	for(int i=1;i<n;i++)cin >> C[i];
	for(int i=1;i<=n;i++){
		cin >> b;
		for(int j=1;j<=b;j++){
			cin >> a;
			kunci[i].push_back(a);
		}
	}
	for(int i=1;i<n;i++){
		for(auto isi : kunci[i]){
			last[isi]=i;
		}
		nearL[i]=last[C[i]];
	}
	for(int i=1;i<=n;i++)last[i]=n+5;
	for(int i=n-1;i>=1;i--){
		for(auto isi : kunci[i+1]){
			last[isi]=i+1;
		}
		nearR[i]=last[C[i]];
	}
	for(int i=1;i<=n;i++){
		kiri[i]=i;kanan[i]=i;
		while(true){
			if(kiri[i]-1>=1 && nearR[kiri[i]-1]<=kanan[i]){
				kanan[i]=max(kanan[i],kanan[kiri[i]-1]);
				kiri[i]=kiri[kiri[i]-1];
			}
			else if(kanan[i]+1<=n && nearL[kanan[i]]>=kiri[i]){
				kanan[i]++;
			}
			else break;
		}
	}
	cin >> q;
	while(q--){
		cin >> a >> b;
		if(b>a){
			if(b<=kanan[a])cout << "YES\n";
			else cout << "NO\n";
		}
		else{
			if(b>=kiri[a])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