Submission #431511

#	Time	Username	Problem	Language	Result	Execution time	Memory
431511		errorgorn	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	221 ms	2792 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,q;
int arr[5005];
vector<int> keys[5005];

bool has[5005];

int l[5005],r[5005];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,2,n+1) cin>>arr[x];
	
	int a,b;
	rep(x,1,n+1){
		cin>>a;
		rep(y,0,a){
			cin>>b;
			keys[x].pub(b);
		}
	}
	
	rep(x,1,n+1){
		swap(arr[x-1],arr[x]);
		
		memset(has,false,sizeof(has));
		for (auto &it:keys[x]) has[it]=true;
		
		int left=x,right=x;
		while (true){
			if (left!=1 && has[arr[left-1]]){
				left--;
				for (auto &it:keys[left]) has[it]=true;
			}
			else if (right!=n && has[arr[right+1]]){
				right++;
				for (auto &it:keys[right]) has[it]=true;
			}
			else break;
		}
		
		//cout<<left<<" "<<right<<endl;
		tie(l[x],r[x])=ii(left,right);
	}
	
	cin>>q;
	
	while (q--){
		cin>>a>>b;
		
		if (b<l[a] || r[a]<b) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
}

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