#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int n,c[maxn],last[maxn],l[maxn],r[maxn],dpl[maxn],dpr[maxn];
vector<int>all[maxn],insl[maxn],dell[maxn],insr[maxn],delr[maxn],ins[maxn],del[maxn];
void vorod(){
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>c[i];
}
for(int i=1;i<=n;i++){
int d;
cin>>d;
all[i].resize(d);
for(int j=0;j<d;j++){
cin>>all[i][j];
}
}
}
void pre(){
for(int i=1;i<n;i++){
for(auto x:all[i]){
last[x]=i;
}
l[i]=last[c[i]];
}
for(int i=1;i<=n;i++){
last[i]=n+3;
}
r[1]=n+3;
for(int i=n;i>=2;i--){
for(auto x:all[i]){
last[x]=i;
}
r[i]=last[c[i-1]];
}
set<int>st;
st.insert(n+1);
insl[1].push_back(1);
for(int i=n;i>=2;i--){
if(i==n||l[i]!=i)
st.insert(i);
for(auto x:del[i]){
st.erase(x);
}
if((*st.begin())>=r[i]){
continue;
}
insl[i].push_back(i);
auto y=st.lower_bound(r[i]);
y--;
auto x=*y;
dell[x].push_back(i);
del[l[i]].push_back(i);
// st.insert(i);
}
st.clear();
for(int i=0;i<=n;i++){
del[i].clear();
}
st.insert(0);
insr[n].push_back(n);
for(int i=1;i<n;i++){
if(i==1||r[i]!=i)
st.insert(i);
for(auto x:del[i]){
st.erase(x);
}
if((*st.rbegin())<=l[i]){
continue;
}
insr[i].push_back(i);
auto y=st.upper_bound(l[i]);
auto x=*y;
delr[x].push_back(i);
del[r[i]].push_back(i);
// st.insert(i);
}
st.clear();
for(int i=1;i<=n;i++){
for(auto x:insl[i]){
st.insert(x);
}
for(auto x:dell[i]){
st.erase(x);
}
dpl[i]=(*st.rbegin());
}
st.clear();
for(int i=n;i>=1;i--){
for(auto x:insr[i]){
st.insert(x);
}
for(auto x:delr[i]){
st.erase(x);
}
dpr[i]=(*st.begin());
}
}
void debug(){
for(int i=1;i<=n;i++){
cout<<i<<" "<<dpl[i]<<" "<<dpr[i]<<" "<<l[i]<<" "<<r[i]<<"\n";
}
}
void solve(){
int q;
cin>>q;
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
if(r>=dpl[l]&&r<=dpr[l]){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vorod();
pre();
// debug();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
93016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
93016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
108308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
93016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
