제출 #1325777

#제출 시각아이디문제언어결과실행 시간메모리
1325777PieArmyLong Mansion (JOI17_long_mansion)C++20
100 / 100
940 ms120540 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)

struct Seg1{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n<<2,-1);
	}
	int l,r,x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void update(int tar,int val){
		l=tar;
		r=val;
		up();
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return n;
		if(tree[node]<x)return n;
		if(left==right){
			return left;
		}
		if(left>=l&&right<=r){
			if(tree[node*2]>=x)return qu(node*2,left,mid);
			return qu(node*2+1,mid+1,right);
		}
		int res=qu(node*2,left,mid);
		if(res==n)res=qu(node*2+1,mid+1,right);
		return res;
	}
	int query(int left,int right,int val){
		l=left;r=right;x=val;
		return qu();
	}
};
struct Seg2{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n<<2,n);
	}
	int l,r,x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=min(tree[node*2],tree[node*2+1]);
	}
	void update(int tar,int val){
		l=tar;
		r=val;
		up();
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return -1;
		if(tree[node]>x)return -1;
		if(left==right){
			return left;
		}
		if(left>=l&&right<=r){
			if(tree[node*2+1]<=x)return qu(node*2+1,mid+1,right);
			return qu(node*2,left,mid);
		}
		int res=qu(node*2+1,mid+1,right);
		if(res==-1)res=qu(node*2,left,mid);
		return res;
	}
	int query(int left,int right,int val){
		l=left;r=right;x=val;
		return qu();
	}
};

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

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;
		}
	}

	mx.init(n+2);
	mn.init(n+2);
	for(int i=0;i<=n+1;i++){
		mx.update(i,ara[i].sc);
		mn.update(i,ara[i].fr);
	}
	for(int i=2;i<=n+1;i++){
		int x=mx.query(ara[i].fr,i-1,i);
		if(x!=n+2){
			if(x+1<=i-1){
				ls[x+1].pb(x+1);
				ls[i].pb(-x-1);
				rs[x+1].pb(i-1);
				rs[i].pb(1-i);
			}
		}
	}
	for(int i=n-1;i>=0;i--){
		int x=mn.query(i+1,ara[i].sc,i);
		if(x!=-1){
			if(i+1<=x-1){
				ls[i+1].pb(i+1);
				ls[x].pb(-i-1);
				rs[i+1].pb(x-1);
				rs[x].pb(1-x);
			}
		}
	}

	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()};
		//cerr<<ara[i].fr<<":"<<ara[i].sc<<" "<<ans[i].fr<<":"<<ans[i].sc<<endl;
	}
	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...