제출 #260672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260672		fadi57	Long Mansion (JOI17_long_mansion)	C++14	0 / 100	1780 ms	32364 KiB

long_mansion

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

const int mx=500020;
int c[mx];
ll b[mx];

vector<ll>keys[mx];
ll mxright[mx];
ll mxleft[mx];
ll n,m;
int leftt[mx];int rightt[mx];
int last[mx];
int canr(int i){
    if(leftt[c[i]]>=mxleft[i]&&leftt[c[i]]!=-1&&mxright[i]<n){
       return 1;
    }return 0;
}int canl(int i){
    if(rightt[c[i-1]]<=mxright[i]&&rightt[c[i]]!=-1&&mxleft[i]>1){
       return 1;
    }return 0;
}
int main()
{
  
  cin>>n;
  for(ll i=1;i<n;i++){
      cin>>c[i];
  }
  
  for(ll i=1;i<=n;i++){
      cin>>b[i];
      for(ll j=0;j<b[i];j++){
          ll x;
          cin>>x;
          keys[i].push_back(x);
      }
  }
  
    memset(last ,-1 ,sizeof last);
    
    for(int i=1;i<n;i++){
        for(int j:keys[i]){
            last[j]=i;
        }
        leftt[c[i]]=last[c[i]];
    } 
    memset(last ,-1 ,sizeof last);
    
      for(int i=n-1;i>=1;i--){
        for(int j:keys[i+1]){
            last[j]=i+1;
        }
       rightt[c[i]]=last[c[i]];
    }
    for(ll i=1;i<=n;i++){
        
       ll myr=i;
        ll myl=i; mxleft[i]=i;  mxright[i]=i;
        while(1){
          ll xx=0;ll xo=0;
       
          if(canr(i)){
              xx=1;
              
              myr++;
            mxright[i]=myr;
             
          }
          if(canl(i)){
              xo=1;
             
             
              myl--;  mxleft[i]=myl;
               mxleft[i]=min(mxleft[i],mxleft[mxleft[i]]);
               mxright[i]=max(mxright[i],mxright[mxleft[i]]);
        
          }
            if(xo||xx){
                
            }else{
                break;
               
            }
        } //mxleft[i]=myl;mxright[i]=myr;
       // cout<<myl<<" "<<myr<<endl;
        //return 0;
     
  }//cout<<mxright[1];
  ll q;cin>>q;
  for(ll i=0;i<q;i++){
      ll x,y;cin>>x>>y;
     //cout<<mxleft[x]<<" "<<mxright[x];
      if(mxleft[x]<=y&&y<=mxright[x]){
         cout<<"YES";
      }else{cout<<"NO";}
      cout<<endl;
  }

}

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