Submission #848605

#	Time	Username	Problem	Language	Result	Execution time	Memory
848605		dungz	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	223 ms	41324 KiB

long_mansion

//#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=5e5+5;
int a[nmax],f[nmax];
vector<int> key[nmax];
int rr[nmax],lll[nmax],exl[nmax],exr[nmax];
void dnc(int l,int r)
{
	if(l==r)
	{
		exl[l]=exr[l]=l;
		return;
	}
	int m=(l+r)/2;
	dnc(l,m);
	dnc(m+1,r);
	int cl=m,cr=m;
	for(int i=m;i>=l;i--)
	{
		if(exr[i]==m)
		{
			cl=min(cl,exl[i]);
			while(1)
			{
				if(cr<r and rr[cr]>=cl) cr++;
				else if(cl>l and lll[cl]<=cr) cl--;
				else break;
			}
			exr[i]=cr,exl[i]=cl;
		}
	}
	cl=m+1,cr=m+1;
	for(int i=m+1;i<=r;i++)
	{
		if(exl[i]==m+1)
		{
			cr=max(cr,exr[i]);
			while(1)
			{
				if(cl>l and lll[cl]<=cr) cl--;
				else if(cr<r and rr[cr]>=cl) cr++;
				else break; 
			}
			exr[i]=cr,exl[i]=cl;
		}
	}
}
int main(){
   	//freopen (task".inp", "r", stdin);
   	//freopen (task".out", "w", stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x;
		for(int j=1;j<=x;j++)
		{
			cin>>y;
			key[i].push_back(y);
		}
	}
//	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		for(auto j:key[i])
		{
			f[j]=i;
		}
		rr[i]=f[a[i]];
	}
	for(int i=0;i<=n;i++) f[i]=n+1;
	for(int i=n;i>=1;i--)
	{
		for(auto j:key[i])
		{
			f[j]=i;
		}
		lll[i]=f[a[i-1]];	
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<rr[i]<<" "<<lll[i]<<endl;
//	}
//	cout<<endl;
	dnc(1,n);
//	for(int i=1;i<=n;i++)
//	{
//		cout<<exl[i]<<" "<<exr[i]<<endl;
//	}
	int q;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		if(exl[x]<=y and exr[x]>=y) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}
/*
5
1 2 3 4
2 2 3
1 1
1 1
1 3
1 4
4
2 4
4 2
1 5
5 3

*/

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