#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;c--;)
cin >> x,v[i].pb(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;
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(int i=1;i<=n;++i)
assert(relL[i]>=1&&relL[i]<=i),assert(relR[i]>=i&&relR[i]<=n),assert(rm[i]>=i&&rm[i]<=n);
for(cin >> q;q--;)
if(cin >> l >> r,l<r)
cout << (relR[l]>=r?"YES":"NO") << "\n";
else
cout << (relL[l]<=r?"YES":"NO") << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
241 ms |
20360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
