| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 131095 | baluteshih | Long Mansion (JOI17_long_mansion) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector<int> v[500005];
int L[500005],R[500005],key[500005],ls[500005];
int rm[500005],relL[500005],relR[500005];
int main()
{jizz
int n,c,x,q,l,r;
cin >> n;
for(int i=1;i<n;++i)
cin >> key[i];
for(int i=1;i<=n;++i)
for(cin >> c,v[i].resize(c);c--;)
cin >> x,v[c]=x;
for(int i=1;i<n;L[i]=ls[key[i]],++i)
for(int j:v[i])
ls[j]=i;
fill(ls+1,ls+n+1,n+1),R[0]=n+1;
for(int i=n-1;i>0;R[i]=ls[key[i]],--i)
for(int j:v[i+1])
ls[j]=i+1;
for(int i=n;i>0;--i)
for(rm[i]=i;L[rm[i]]>=i;rm[i]=rm[rm[i]+1]);
for(int i=1;i<=n;++i)
if(R[i-1]>rm[i])
relL[i]=i,relR[i]=rm[i];
else
for(relL[i]=relL[i-1],relR[i]=max(rm[i],relR[i-1]);L[relR[i]]>=relL[i]||R[relL[i]-1]<=relR[i];)
if(L[relR[i]]>=relL[i])
relR[i]=rm[relR[i]+1];
else if(R[relL[i]-1]<=relR[i])
relL[i]=relL[relL[i]-1],relR[i]=max(relR[i],relR[relL[i]]);
for(cin >> q;q--;)
if(cin >> l >> r,relL[l]<=r&&relR[l]>=r)
cout << "YES\n";
else
cout << "NO\n";
}