Submission #431375

#	Time	Username	Problem	Language	Result	Execution time	Memory
431375		kai824	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3072 ms	26400 KiB

long_mansion

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

typedef pair<int,int> pii;
#define f first
#define s second

int last[500005],l[500005],r[500005];
int c[500005];
vector<int> v[500005];
pii rng[500005];//range...

void aq(){//to be kept for later...
  int q,a,b;
  cin>>q;
  while(q--){
    cin>>a>>b;
    a--;b--;
    if(rng[a].f<=b && b<=rng[a].s){
      cout<<"YES\n";
    }else cout<<"NO\n";
  }
}
int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int n,a;
  cin>>n;
  for(int i=0;i+1<n;i++){
    cin>>c[i];
  }
  for(int i=0;i<n;i++){
    cin>>a;
    v[i].resize(a);
    for(int j=0;j<a;j++){
      cin>>v[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    last[i]=-1;
  }
  for(int i=0;i+1<n;i++){//l[node]: nearest left node of same key...
    for(int x:v[i]){
      last[x]=i;
    }
    l[i]=last[c[i]];
  }
  for(int i=1;i<=n;i++)last[i]=1e9;
  for(int i=n-2;i>=0;i--){
    for(int x:v[i+1]){
      last[x]=i+1;
    }
    r[i]=last[c[i]];
  }

  for(int i=0;i<n;i++){
    rng[i].f=rng[i].s=i;
    while(true){
      bool br=true;
      while(rng[i].f>0 && r[rng[i].f-1]<=rng[i].s)rng[i].f--,br=false;
      while(rng[i].s+1<n && l[rng[i].s]>=rng[i].f)rng[i].s++,br=false;
      if(br)break;
    }
  }

  aq();
  return 0;
}

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