Submission #322014

#	Time	Username	Problem	Language	Result	Execution time	Memory
322014		GioChkhaidze	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	846 ms	119148 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;
 
const int N=5e5+5;

int n,q,x,y;
int a[N],sz[N];
int L[N],R[N],ansl[N],ansr[N];

set < int > st[N];
set < int > :: iterator it;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL),cout.tie(NULL);
  
  cin>>n;
  for (int i=1; i<n; i++)
    cin>>a[i];
  
  for (int i=1; i<=n; i++) {
    cin>>sz[i];
    for (int j=1; j<=sz[i]; j++) {
      cin>>x;
      st[x].insert(i);
    }
  }
  
  for (int i=1; i<=n; i++)
    st[i].insert(-1),st[i].insert(n+1);
  
  for (int i=1; i<n; i++) {
    it=st[a[i]].upper_bound(i);
    R[i]=(*it);
    --it;
    L[i]=(*it);
  }

  for (int i=1; i<=n; i++) {
    ansl[i]=ansr[i]=i;
    while (1) {
      if (1<ansl[i] && R[ansl[i]-1]<=ansr[i]) {
        ansr[i]=max(ansr[i],ansr[ansl[i]-1]);
        ansl[i]=min(ansl[i],ansl[ansl[i]-1]);
      }
        else
      if (ansr[i]<=n && ansl[i]<=L[ansr[i]]) {
        ansr[i]++;
      }
        else break;
    }
  }
  
  cin>>q;
  while (q--) {
    cin>>x>>y;
    if (ansl[x]<=y && y<=ansr[x])
      cout<<"YES\n";
        else
      cout<<"NO\n";
  }
}

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