Submission #120368

#	Time	Username	Problem	Language	Result	Execution time	Memory
120368		shayan_p	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	196 ms	17784 KiB

long_mansion

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10,mod=1e9+7;
const ll inf=1e18;

int c[maxn];
vector<int> v[maxn];
int lst[maxn], aft[maxn],bef[maxn], L[maxn], R[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int n; cin>>n;

    for(int i=1;i<=n-1;i++){
	cin>>c[i];
    }
    for(int i=1;i<=n;i++){
	int s; cin>>s;
	while(s--){
	    int x; cin>>x;
	    v[i].PB(x);
	}
    }
    bef[n+1]=0, aft[0]=n+1;
    
    for(int i=0;i<=n;i++){
	lst[i]=n+1;
    }
    for(int i=n;i>=1;i--){
	aft[i]=lst[c[i]];
	for(int x:v[i])
	    lst[x]=i;
    }

    for(int i=0;i<=n;i++){
	lst[i]=0;
    }
    for(int i=1;i<=n;i++){
	bef[i]=lst[ c[i-1] ];
	for(int x:v[i])
	    lst[x]=i;
    }
    for(int i=1;i<=n;i++){
	L[i]=1, R[i]=n;
    }
    
    for(int i=1;i<=n;i++){
	int id=-1;
	for(int j=i-1;j>=bef[i];j--){
	    if(aft[j]>=i) id=j;
	}
	if(id!=-1){
	    for(int j=id+1;j<i;j++)
		R[j]= min( R[j], i-1); 
	}

	id=-1;
	for(int j=i+1;j<=aft[i];j++){
	    if(bef[j]<=i) id=j;
	}
	if(id!=-1){
	    for(int j=i+1;j<id;j++)
		L[j]= max( L[j], i+1);
	}
    }

    int q; cin>>q;
    while(q--){
	int a,b; cin>>a>>b;
	cout<<( L[a]<=b && b<=R[a] ? "YES\n" : "NO\n" );
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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