//1L1YA
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define Pb push_back
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define all(x) x.begin(),x.end()
#define al(x,n) x+1,x+n+1
#define SZ(x) ((int)x.size())
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r>>1)
#define dokme(x) cout << x << endl, exit(0)
#define sik(x) cout << x << endl;continue;
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=5e5+11;
const int lg=23;
int n,m,q,a[N],l[N],r[N],lst[N];
vector<int> vc[N],vec[N];
pii val[N],seg[N<<2];
void build(int id=1,int l=1,int r=n+1){
seg[id]={1,n};
if(r-l==1) return;
build(lc,l,mid);
build(rc,mid,r);
}
void update(int ql,int qr,pii val,int id=1,int l=1,int r=n+1){
if(qr<=l || ql>=r) return;
if(ql<=l && r<=qr){
seg[id].F=max(seg[id].F,val.F);
seg[id].S=min(seg[id].S,val.S);
return;
}
update(ql,qr,val,lc,l,mid);
update(ql,qr,val,rc,mid,r);
}
pii get(int pos,int id=1,int l=1,int r=n+1){
if(r-l==1) return seg[id];
pii p;
if(pos<mid) p=get(pos,lc,l,mid);
else p=get(pos,rc,mid,r);
return {max(p.F,seg[id].F),min(p.S,seg[id].S)};
}
int main(){
FastIO
cin >> n;
for(int i=1;i<n;i++) cin >> a[i];
for(int i=1;i<=n;i++){
cin >> m;
for(int j=1;j<=m;j++){
int x;cin >> x;
vc[i].Pb(x);
}
}
for(int i=1;i<n;i++){
for(int j: vc[i]) lst[j]=i;
l[i]=lst[a[i]];
}
fill(lst,lst+n+1,n+1);
for(int i=n;i>1;i--){
for(int j: vc[i]) lst[j]=i;
r[i-1]=lst[a[i-1]];
vec[r[i-1]].Pb(i);
}
build();
set<int> st;
for(int i=1;i<=n;i++){
for(int j: vec[i]) st.erase(j);
if(SZ(st)){
auto it=st.upper_bound(l[i]);
if(it!=st.end()) update(*it,i+1,{*it,i});
}
st.insert(i+1);
}
st.clear();
for(int i=0;i<=n+1;i++) vec[i].clear();
for(int i=1;i<n;i++) vec[l[i]].Pb(i);
r[0]=n+1;
for(int i=n;i;i--){
for(int j: vec[i]) st.erase(j);
if(SZ(st)){
auto it=st.lower_bound(r[i-1]);
if(it--!=st.begin()) update(i,(*it)+1,{i,*it});
}
st.insert(i-1);
}
for(int i=1;i<=n;i++) val[i]=get(i);
cin >> q;
while(q--){
int x,y;
cin >> x >> y;
if(y>=val[x].F && y<=val[x].S) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
Compilation message
long_mansion.cpp: In function 'void build(int, int, int)':
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:44:13: note: in expansion of macro 'mid'
44 | build(lc,l,mid);
| ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:45:11: note: in expansion of macro 'mid'
45 | build(rc,mid,r);
| ^~~
long_mansion.cpp: In function 'void update(int, int, pii, int, int, int)':
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:55:24: note: in expansion of macro 'mid'
55 | update(ql,qr,val,lc,l,mid);
| ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:56:22: note: in expansion of macro 'mid'
56 | update(ql,qr,val,rc,mid,r);
| ^~~
long_mansion.cpp: In function 'pii get(int, int, int, int)':
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:62:9: note: in expansion of macro 'mid'
62 | if(pos<mid) p=get(pos,lc,l,mid);
| ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:62:29: note: in expansion of macro 'mid'
62 | if(pos<mid) p=get(pos,lc,l,mid);
| ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | #define mid (l+r>>1)
| ~^~
long_mansion.cpp:63:20: note: in expansion of macro 'mid'
63 | else p=get(pos,rc,mid,r);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
9 ms |
33636 KB |
Output is correct |
| 3 |
Correct |
8 ms |
33628 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
9 ms |
33636 KB |
Output is correct |
| 3 |
Correct |
8 ms |
33628 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
50800 KB |
Output is correct |
| 2 |
Correct |
164 ms |
50728 KB |
Output is correct |
| 3 |
Correct |
137 ms |
50512 KB |
Output is correct |
| 4 |
Correct |
151 ms |
50628 KB |
Output is correct |
| 5 |
Correct |
147 ms |
50612 KB |
Output is correct |
| 6 |
Correct |
128 ms |
49748 KB |
Output is correct |
| 7 |
Correct |
105 ms |
49744 KB |
Output is correct |
| 8 |
Correct |
111 ms |
49744 KB |
Output is correct |
| 9 |
Correct |
137 ms |
49748 KB |
Output is correct |
| 10 |
Correct |
104 ms |
49748 KB |
Output is correct |
| 11 |
Correct |
103 ms |
49632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
9 ms |
33636 KB |
Output is correct |
| 3 |
Correct |
8 ms |
33628 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
