제출 #697097

#제출 시각아이디문제언어결과실행 시간메모리
697097amunduzbaevLong Mansion (JOI17_long_mansion)C++17
25 / 100
3077 ms52484 KiB
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

const int N = 5e5 + 5;
int c[N], b[N], last[N];
vector<int> a[N];
int l[N], r[N];
int L[N], R[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	for(int i=1;i<n;i++){
		cin >> c[i];
	}
	
	for(int i=1;i<=n;i++){
		cin >> b[i];
		L[i] = 1, R[i] = n;
		a[i].resize(b[i]);
		for(int j=0;j<b[i];j++){
			cin >> a[i][j];
		}
	}
	
	for(int i=0;i<N;i++) last[i] = 0;
	for(int i=1;i<=n;i++){
		for(auto x : a[i]){
			last[x] = i;
		}
		l[i] = last[c[i]];
	}
	for(int i=0;i<N;i++) last[i] = n + 1;
	for(int i=n;i>0;i--){
		r[i] = last[c[i]];
		for(auto x : a[i]){
			last[x] = i;
		}
	}
	r[0] = N, l[n] = 0;
	for(int i=1;i<n;i++){
		int j = r[i] - 1;
		for(;i < j;j--){
			if(l[j] <= i){
				break;
			}
		}
		
		if(i < j && l[j] <= i){
			for(int k=i+1;k<=j;k++){
				L[k] = max(L[k], i + 1);
			}
		}
		
		j = l[i];
		for(;j < i;j++){
			if(i < r[j]){
				break;
			}
		}
		
		if(j < i && i < r[j]){
			for(int k=j+1;k<=i;k++){
				R[k] = min(R[k], i);
			}
		}
	}
	
	//~ for(int i=1;i<=n;i++){
		//~ cout<<L[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=1;i<=n;i++){
		//~ cout<<R[i]<<" ";
	//~ } cout<<"\n";
	
	int q; cin >> q;
	while(q--){
		int a, b; cin >> a >> b;
		if(L[a] <= b && b <= R[a]){
			cout<<"YES\n";
		} else {
			cout<<"NO\n";
		}
	}
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...