#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
using namespace std;
const int NMAX = 500000 + 5;
int n,q;
int c[NMAX];
vector<int> a[NMAX];
vector<int> pos[NMAX];
int lef[NMAX], rig[NMAX];
bool inside(int l, int r, int key)
{
if (key <= 0 || key >= NMAX) return false;
auto &v = pos[key];
if (v.empty()) return false;
auto it = lower_bound(v.begin(), v.end(), l);
return it!=v.end() && *it <= r;
}
void input()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin>>n)) exit(0);
FOR(i,1,n-1) cin>>c[i];
FOR(i,1,n)
{
int b; cin>>b;
a[i].resize(b);
FOR(j,0,b-1)
{
cin>>a[i][j];
if (a[i][j] >= 0 && a[i][j] < NMAX) pos[a[i][j]].push_back(i);
}
}
cin>>q;
}
void solve()
{
FOR(i,1,n)
{
lef[i]=rig[i]=i;
bool nxt = true;
while(nxt)
{
nxt = false;
while (lef[i] > 1 && inside(lef[i], rig[i], c[lef[i]-1]) )
{
int L = lef[lef[i]-1];
int R = rig[lef[i]-1];
lef[i] = L;
if (R > rig[i]) rig[i] = R;
nxt = true;
}
while (rig[i] < n && inside(lef[i], rig[i], c[rig[i]]))
{
rig[i]++;
if (rig[i] < i)
{
if (lef[rig[i]] < lef[i]) lef[i] = lef[rig[i]];
if (rig[rig[i]] > rig[i]) rig[i] = rig[rig[i]];
}
nxt = true;
}
}
}
while(q--)
{
int x,y; cin>>x>>y;
if (x<=y)
{
if (lef[x] <= y && y <= rig[x]) cout<<"YES\n";
else cout<<"NO\n";
}else
{
if (lef[x] <= y && y <= rig[x]) cout<<"YES\n";
else cout<<"NO\n";
}
}
}
signed main()
{
input();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |