#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=5e5+5;
int lst[nax];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
vector<int> tab[2*n];
for (int i = 0; i < n-1; ++i)
{
int x;
cin>>x;
tab[i*2+1].push_back(x);
}
for (int i = 0; i < n; ++i)
{
int x;
cin>>x;
for (int j = 0; j < x; ++j)
{
int y;
cin>>y;
tab[i*2].push_back(y);
}
}
for (int i = 0; i < nax; ++i) lst[i]=-1;
vector <pair<pair<int,int>,int>> cnt;
for (int i = 0; i < 2*n-1; ++i)
{
if(i%2){
cnt.push_back({{i,0},lst[tab[i][0]]});
}else{
for(auto u:tab[i]) {
lst[u]=i;
}
}
}
for (int i = 0; i < 2*n-1; ++i) lst[i]=2*n-1;
for (int i = 2*n-2; i >= 0; --i)
{
if(i%2){
cnt.push_back({{i,1},lst[tab[i][0]]});
}else{
for(auto u:tab[i]) lst[u]=i;
}
}
cnt.push_back({{-1,1},2*n-1});
cnt.push_back({{2*n-1,0},-1});
sort(cnt.begin(),cnt.end());
//for(auto u:cnt) cout <<u.fi.fi<<" "<<u.se<<" "<<u.fi.se<<endl;
stack<pair<int,int>> st;
vector<pair<int,int>> intersection;
vector<pair<int,int>> ans(2*n);
for (int i = 0; i < 2*n; ++i) ans[i]={-1,2*n-1};
int lst = -1;
for (int i = 0; i < cnt.size(); ++i)
{
if(cnt[i].fi.se==1) {
st.push({cnt[i].fi.fi,cnt[i].se});
}else{
while(!st.empty()&&st.top().se<cnt[i].fi.fi){
st.pop();
}
pair<int,int> nab={-1,-1};
if(!st.empty()) nab=st.top();
bool test=false;
int y = cnt[i].fi.fi;
//cout <<y<<endl;
while(!st.empty()){
while(!st.empty()&&st.top().se<cnt[i].fi.fi){
st.pop();
}if(st.empty()) break;
if(st.top().fi<cnt[i].se){
if(!test) nab={-1,-1};
break;
}
test=true;
int x = y;
while(x > max(st.top().fi,lst) ){
if(x%2==0){
ans[x]={st.top().fi,cnt[i].fi.fi};
}
x--;
}
y=x;
intersection.push_back({st.top().fi,cnt[i].fi.fi});
st.pop();
}
if(nab!=make_pair(-1,-1)){
st.push(nab);
lst=cnt[i].fi.fi;
}
}
}
//for(auto u:intersection) cout << u.fi <<" "<<u.se<<endl;
sort(intersection.begin(),intersection.end());
//for(auto u:intersection) cout <<u.fi<<" "<<u.se<<endl;
int q;
cin>>q;
for (int i = 0; i < q; ++i)
{
int l,r;
cin>>l>>r;
l--;r--;
l*=2;
r*=2;
if(ans[l].fi<=r&&r<=ans[l].se) cout <<"YES"<<endl;
else cout <<"NO"<<endl;
/*int cur=lower_bound(intersection.begin(),intersection.end(),make_pair(l,0))-intersection.begin();
cur--;
cur=lower_bound(intersection.begin(),intersection.end(),make_pair(intersection[cur].fi,l))-intersection.begin();
cout<< cur<<" "<<intersection[cur].fi<<" "<<intersection[cur].se<<endl;
if(intersection[cur].fi<=r&&r<=intersection[cur].se) cout <<"YES"<<endl;
else cout << "NO" <<endl;*/
}
}
Compilation message (stderr)
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |