Submission #1240050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240050		lioow	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	500 ms	35424 KiB

long_mansion

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;
const int maxn=5e5;
vector<int>pos[maxn+2];
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;cin>>n;
	int c[n+2];
	pii lr[n+2];
	for(int i=1;i<=n-1;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		lr[i]={i,i};
	}
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		for(int j=1;j<=k;j++){
			int x;cin>>x;
			pos[x].pb(i);
		}
	}
	for(int i=1;i<=n;i++){
		while(1){
			if(lr[i].fi!=1){
				auto x=lower_bound(all(pos[c[lr[i].fi-1]]),lr[i].fi);
				if(x!=pos[c[lr[i].fi-1]].end() && (*x)<=lr[i].se){
					lr[i].se=max(lr[i].se,lr[lr[i].fi-1].se);
					lr[i].fi=min(lr[i].fi,lr[lr[i].fi-1].fi);
					continue;
				}
			}
			if(lr[i].se!=n){
				auto x=lower_bound(all(pos[c[lr[i].se]]),lr[i].fi);
				if(x!=pos[c[lr[i].se]].end() && (*x)<=lr[i].se){
					lr[i].fi=min(lr[i].fi,lr[lr[i].se+1].fi);
					lr[i].se=max(lr[i].se,lr[lr[i].se+1].se);
					continue;
				}
			}
			break;
		}
	}
	int q;cin>>q;
	while(q--){
		int x,y;cin>>x>>y;
		if(lr[x].fi<=y && y<=lr[x].se) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

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