제출 #1325761

#제출 시각아이디문제언어결과실행 시간메모리
1325761PieArmyLong Mansion (JOI17_long_mansion)C++20
0 / 100
126 ms20640 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n;
int need[500023];
vector<int>v[500023];
int las[500023];
pair<int,int>ara[500023],ans[500023];
vector<int>sta;
vector<int>ls[500023],rs[500023];
multiset<int,greater<int>>l;
multiset<int>r;

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>need[i];
	}
	for(int i=1;i<=n;i++){
		int s;cin>>s;
		v[i].resize(s);
		for(int j=0;j<s;j++){
			cin>>v[i][j];
		}
	}
	for(int i=0;i<=n;i++){
		las[i]=0;
	}
	for(int i=1;i<=n+1;i++){
		ara[i].fr=las[need[i-1]];
		for(int x:v[i]){
			las[x]=i;
		}
	}
	for(int i=0;i<=n;i++){
		las[i]=n+1;
	}
	for(int i=n+1;i>=0;i--){
		ara[i].sc=las[need[i]];
		for(int x:v[i]){
			las[x]=i;
		}
	}
	sta.pb(0);
	for(int i=1;i<=n+1;i++){
		while(ara[sta.back()].sc<i)sta.pop_back();
		int l=0,r=sta.size();
		while(l<r){
			int mi=(l+r)/2;
			if(sta[mi]>=ara[i].fr)r=mi;
			else l=mi+1;
		}
		if(l!=sta.size()&&sta[l]+1<=i-1){
			ls[sta[l]+1].pb(sta[l]+1);
			ls[i].pb(-sta[l]-1);
			rs[sta[l]+1].pb(i-1);
			rs[i].pb(1-i);
		}
		while(ara[sta.back()].sc<ara[i].sc)sta.pop_back();
		sta.pb(i);
	}
	sta.clear();

	sta.pb(n+1);
	for(int i=n;i>=0;i--){
		while(ara[sta.back()].fr>i)sta.pop_back();
		int l=0,r=sta.size();
		while(l<r){
			int mi=(l+r)/2;
			if(sta[mi]<=ara[i].sc)r=mi;
			else l=mi+1;
		}
		if(l!=sta.size()&&i+1<=sta[l]-1){
			ls[i+1].pb(i+1);
			ls[sta[l]].pb(-i-1);
			rs[i+1].pb(sta[l]-1);
			rs[sta[l]].pb(1-sta[l]);
		}
		while(ara[sta.back()].fr>ara[i].fr)sta.pop_back();
		sta.pb(i);
	}
	sta.clear();

	for(int i=1;i<=n;i++){
		for(int x:ls[i]){
			if(x<0)l.erase(l.find(-x));
			else l.insert(x);
		}
		for(int x:rs[i]){
			if(x<0)r.erase(r.find(-x));
			else r.insert(x);
		}
		ans[i]={*l.begin(),*r.begin()};
	}
	int q;cin>>q;
	while(q--){
		int x,y;cin>>x>>y;
		if(y>=ans[x].fr&&y<=ans[x].sc)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...