제출 #784904

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

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
 
int n;
int it[500001];
int cur[500001];
int le[500001];
int re[500001];
vector<int> pre[500001];
int tree[4*500001][2];
pair<int,int> tree2[4*500001];
void build(int no,int l,int r){
	if(l==r){
		tree[no][0]=le[l];
		tree[no][1]=re[l];
		tree2[no]={l,l};
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
		tree2[no].a=tree2[no*2+1].a;
		tree2[no].b=tree2[no*2+2].b;
	}
}
pair<int,int> query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return {n,0}; 
	}
	if(aa<=l and r<=bb){
		return tree2[no];
	}
	int mid=(l+r)/2;
	pair<int,int> x=query(no*2+1,l,mid,aa,bb);
	pair<int,int> y=query(no*2+2,mid+1,r,aa,bb);
	return {min(x.a,y.a),max(x.b,y.b)};
}
void update(int no,int l,int r,int i,pair<int,int> x){
	if(l==r){
		tree2[no]=x;
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,x);
		}
		else{
			update(no*2+2,mid+1,r,i,x);
		}
		tree2[no].a=min(tree2[no*2+1].a,tree2[no*2+2].a);
		tree2[no].b=max(tree2[no*2+1].b,tree2[no*2+2].b);
	}
}
int query2(int no,int l,int r,int i,int x){
	if(r<i){
		return r+1;
	}
	if(l==r and tree[no][0]<x){
		return l;
	}
	if(tree[no][0]>=x){
		return r+1;
	}
	int mid=(l+r)/2;
	int xx=query2(no*2+1,l,mid,i,x);
	if(xx==mid+1){
		return query2(no*2+2,mid+1,r,i,x);
	}
	return xx;
}
int query3(int no,int l,int r,int i,int x){
	//return largest index<=i with r value >x
	if(l>i){
		return l-1;
	}
	if(l==r and tree[no][1]>x){
		return l;
	}
	if(tree[no][1]<=x){
		return l-1;
	}
	int mid=(l+r)/2;
	int xx=query3(no*2+2,mid+1,r,i,x);
	if(xx==mid){
		return query3(no*2+1,l,mid,i,x);
	}
	return xx;

}
pair<int,int> ans[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];
		it[i]--;
	}
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		for(int j=0;j<x;j++){
			int y;
			cin>>y;
			y--;
			pre[i].pb(y);
		}
	}
	for(int i=0;i<n;i++){
		cur[i]=-1;
	}
	le[0]=-1;
	for(int i=0;i<n;i++){
		if(i>0){
			le[i]=cur[it[i-1]];
		}
		for(auto j:pre[i]){
			cur[j]=i;
		}
	}
	re[n-1]=n+1;
	for(int i=0;i<n;i++){
		cur[i]=n+1;
	}
	for(int i=n-1;i>=0;i--){
		if(i<n-1){
			re[i]=cur[it[i]];
		}
		for(auto j:pre[i]){
			cur[j]=i;
		}
	}
	build(0,0,n-1);
/*	for(int i=0;i<n;i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	for(int i=0;i<n;i++){
		pair<int,int> cur={i,i};
		while(true){
			pair<int,int> cur2=cur;
			if(cur.b<n-1){
				int ind=query2(0,0,n-1,cur.b+1,cur.a);
				ind--;
				if(ind>cur.b){
					cur.b=ind;
				}
				cur=query(0,0,n-1,cur.a,cur.b);
			}
			if(cur.a>0){
				int ind=query3(0,0,n-1,cur.a-1,cur.b);
				/*if(i==1){
					cout<<cur.a<<":"<<cur.b<<endl;
					cout<<ind<<"::"<<endl;
				}*/
				ind++;
				if(ind<cur.a){
					cur.a=ind;
				}
				cur=query(0,0,n-1,cur.a,cur.b);
			}
			/*if(i==3){
					cout<<cur.a<<"::"<<cur.b<<endl;
			}*/
			if(cur2.a==cur.a and cur2.b==cur.b){
				break;
			}
		}
		ans[i]=cur;
		update(0,0,n-1,i,cur);
		//cout<<cur.a<<":"<<cur.b<<endl;

	}
		int q;
		cin>>q;
		while(q--){
			int x,y;
			cin>>x>>y;
			x--;
			y--;
			if(ans[x].a<=y and ans[x].b>=y){
				cout<<"YES"<<endl;
			}
			else{
				cout<<"NO"<<endl;
			}
		}



 
 
 
	return 0;
}

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