제출 #120378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120378		shayan_p	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	875 ms	57976 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=5e5+10,inf=1e9;

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

struct Segmentf{
    int mx[4*maxn], mn[4*maxn];
    void build(int *arr,int *arr2,int l=0,int r=n+2,int id=1){
	if(r-l==1){
	    mx[id]= arr[l];
	    mn[id]= arr2[l];
	    return;
	}
	int mid=(l+r)>>1;
	build(arr,arr2,l,mid,2*id);
	build(arr,arr2,mid,r,2*id+1);
	mx[id]= max( mx[2*id], mx[2*id+1]);
	mn[id]= min( mn[2*id], mn[2*id+1]);
    }
    int askgr(int f,int s,int x,int l=0,int r=n+2,int id=1){
	if(f>=s || l>=r || s<=l || r<=f) return -1;
	if(mx[id]<x) return -1;
	if(f<=l && r<=s){
	    if(r-l==1) return l;
	    
	    int mid=(l+r)>>1;
	    if(mx[2*id]<x) return askgr(f,s,x,mid,r,2*id+1);
	    return askgr(f,s,x,l,mid,2*id);
	}
	int mid=(l+r)>>1;
	int num= askgr(f,s,x,l,mid,2*id);
	if(num!=-1) return num;
	return askgr(f,s,x,mid,r,2*id+1);
    }
    int askls(int f,int s,int x,int l=0,int r=n+2,int id=1){
	if(f>=s || l>=r || s<=l || r<=f) return -1;
	if(mn[id]>x) return -1;
	if(f<=l && r<=s){
	    if(r-l==1) return l;
	    
	    int mid=(l+r)>>1;
	    if(mn[2*id+1]>x) return askls(f,s,x,l,mid,2*id);
	    return askls(f,s,x,mid,r,2*id+1);
	}
	int mid=(l+r)>>1;
	int num= askls(f,s,x,mid,r,2*id+1);
	if(num!=-1) return num;
	return askls(f,s,x,l,mid,2*id);
    }
};
Segmentf sf;

struct Segmentv{
    int lz[4*maxn];
    void build(int l=1,int r=n+1,int id=1){
	lz[id]=-inf;
	if(r-l==1) return;
	int mid=(l+r)>>1;
	build(l,mid,2*id);
	build(mid,r,2*id+1);
    }
    void add(int f,int s,int x,int l=1,int r=n+1,int id=1){
	if(f>=s || l>=r || s<=l || r<=f) return;
	if(f<=l && r<=s) { lz[id]=max(lz[id],x); return; }
	int mid=(l+r)>>1;
	add(f,s,x,l,mid,2*id);
	add(f,s,x,mid,r,2*id+1);
    }
    int ask(int pos, int l=1,int r=n+1,int id=1){
	if(r-l==1) return lz[id];
	int mid=(l+r)>>1, num;
	if(pos<mid) num= ask(pos,l,mid,2*id);
	else        num= ask(pos,mid,r,2*id+1);
	return max( num, lz[id]);
    }
};
Segmentv svl, svr;

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

    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);
	}
    }
    */
    sf.build(aft,bef);
    svl.build(), svr.build();
    
    for(int i=1;i<=n;i++){
	int id= sf.askgr(bef[i],i,i);
	if(id!=-1) svr.add(id+1,i, -(i-1) );

	id= sf.askls(i+1,aft[i]+1,i);
	if(id!=-1) svl.add(i+1,id, i+1 );
    }
    for(int i=1;i<=n;i++){
	L[i]= svl.ask(i);
	R[i]=-svr.ask(i);
	L[i]=max(L[i],1);
	R[i]=min(R[i],n);
    }
    

    /*   for(int i=1;i<=n;i++){
	cout<<"HELLO "<<L[i]<<" "<<R[i]<<endl;
	}*/
    
    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: 75 / 75