제출 #346810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346810		kshitij_sodani	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3064 ms	59420 KiB

long_mansion

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int it[500001];
set<int> ss[500001];
int n;
pair<int,int> ans[500001];
vector<int> pre[500001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n-1;i++){
		cin>>it[i];
	}
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		for(int j=0;j<x;j++){
			int aa;
			cin>>aa;
			ss[aa].insert(i);
		}
	}
	set<int> xx;
	for(int i=1;i<n;i++){
		auto j=ss[it[i-1]].upper_bound(i-1);
		if(j==ss[it[i-1]].begin()){
			xx.insert(i);
			//cout<<i<<",,";
		}
		else{
			j--;
			pre[*j].pb(i);
		}
	}
	//cout<<endl;

	for(int i=0;i<n;i++){
		auto j=xx.upper_bound(i);
		if(j==xx.end()){
			ans[i]={i,n-1};
		}
		else{
			ans[i]={i,(*j)-1};
		}
		//cout<<ans[i].a<<":"<<ans[i].b<<endl;
		if(i>0){
			pair<int,int> cur=ans[i];
			while(cur.a>0){
				auto ac=ss[it[cur.a-1]].lower_bound(cur.a);
				if(ac==ss[it[cur.a-1]].end()){
					break;
				}
				/*if(i==3){
					cout<<(*ac)<<endl;
				}*/
				if((*ac)>cur.b){
					break;
				}

				pair<int,int> cur2=ans[cur.a-1];

				ans[i].a=min(ans[i].a,cur2.a);
				ans[i].b=max(ans[i].b,cur2.a);
		//		cout<<cur2.a<<"::"<<cur2.b<<endl;
			/*	if(cur2.b>=i){
					break;
				}*/
				int yy=ans[i].b;
				for(int ii=yy+1;ii<n;ii++){
					auto j=ss[it[ii-1]].lower_bound(ans[i].a);
					/*if(i==1){
						cout<<ii<<"<<<<<"<<endl;
					}*/
					if(j==ss[it[ii-1]].end()){
						break;
					}

					if((*j)<=ans[i].b){

						ans[i].b+=1;
						continue;
					}
					break;
				}
				cur=ans[i];
				continue;
			}
		}
		//cout<<ans[i].a<<","<<ans[i].b<<endl;
		for(auto j:pre[i]){
			xx.insert(j);
		}
	}
	int q;
	cin>>q;
	while(q--){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		if(bb>=ans[aa].a and bb<=ans[aa].b){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}


 
	return 0;
}

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