#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
const int mod2=998244353;
const int mod1=998244353;
struct icd
{
int a,b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c, d,e,f;
};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
/// fin(task),fou(task);
#endif
NHP
/// cin>>s1;
///modwwe
phongbeo();
}
struct IT
{
int t[2000001];
void upd(int node,int l,int r,int l1,int r1,int c )
{
if(l1>r1) return;
if(l>r1||r<l1)return;
if(l>=l1&&r<=r1)
{
t[node]=c;
return;
}
if(t[node]!=0)
{
t[node<<1]=t[node];
t[node<<1|1]=t[node];
t[node]=0;
}
int mid=l+r>>1;
upd(node<<1,l,mid,l1,r1,c);
upd(node<<1|1,mid+1,r,l1,r1,c);
}
int get(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1) return t[node];
if(t[node]!=0)
{
t[node<<1]=t[node];
t[node<<1|1]=t[node];
t[node]=0;
}
int mid=l+r>>1;
return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1);
}
} st1,st2;
struct IT2
{
int t[2000001];
void reset(int node,int l,int r)
{
t[node]=n+1;
if(l==r) return;
int mid=l+r>>1;
reset(node<<1,l,mid);
reset(node<<1|1,mid+1,r);
}
void upd(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return ;
if(l>=l1&&r<=r1)
{
t[node]=l;
return;
}
int mid=l+r>>1;
upd(node<<1,l,mid,l1,r1);
upd(node<<1|1,mid+1,r,l1,r1);
t[node]=max(t[node<<1],t[node<<1|1]);
}
void upd2(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return ;
if(l>=l1&&r<=r1)
{
t[node]=l;
return;
}
int mid=l+r>>1;
upd2(node<<1,l,mid,l1,r1);
upd2(node<<1|1,mid+1,r,l1,r1);
t[node]=min(t[node<<1],t[node<<1|1]);
}
int get2(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return n+1;
if(l>=l1&&r<=r1)return t[node];
int mid=l+r>>1;
return min(get2(node<<1,l,mid,l1,r1),get2(node<<1|1,mid+1,r,l1,r1));
}
int get(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1)return t[node];
int mid=l+r>>1;
return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
}
} ss;
int a[500001];
ib b[500001];
vector<int> v[500001];
vector<int> v2[500001];
vector<int> v3[500001];
void setup()
{
st1.upd(1,1,n,1,n,1);
st2.upd(1,1,n,1,n,n);
for(int i=1; i<n; i++)
{
s2=upper_bound(v[a[i]].begin(),v[a[i]].end(),i)-v[a[i]].begin();
s2--;
s3=v[a[i]][s2]+1;
b[i].a=s3;
v2[s3].pb(i);
s2=lower_bound(v[a[i]].begin(),v[a[i]].end(),i+1)-v[a[i]].begin();
s3=v[a[i]][s2]-1;
b[i].b=s3;
v3[s3].pb(i);
}
}
void solve1()
{
for(int i=1; i<n; i++)
{
/// di tu trai sang
s3=b[i].b;
///i+1->s3
for(auto x:v2[i]) ss.upd(1,1,n,x,x);
if(s3>n)
{
st1.upd(1,1,n,i+1,n,i+1);
continue;
}
if(i+1>s3) continue;
s4=ss.get(1,1,n,i+1,s3);
st1.upd(1,1,n,i+1,s4-1,i+1);
/// cout<<i+1<<" "<<s4<<" "<<b[i].b,down
}
}
void solve2()
{
ss.reset(1,1,n);
for(int i=n-1; i>=1; --i)
{
s3=b[i].a;
for(auto x:v3[i]) ss.upd2(1,1,n,x,x);
if(s3==0)
{
st2.upd(1,1,n,1,i,i);
continue;
}
if(s3>i) continue;
s4=ss.get2(1,1,n,s3,i-1);
st2.upd(1,1,n,s4+1,i,i);
}
}
void phongbeo()
{
cin>>n;
for(int i=1; i<n; i++)
cin>>a[i],v[i].pb(-1);
v[n].pb(-1);
for(int i=1; i<=n; i++)
{
cin>>k;
for(int j=1; j<=k; j++)
{
cin>>l;
v[l].pb(i);
}
}
for(int i=1; i<=n; i++)
v[i].pb(n+3);
setup();
solve1();
solve2();
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>l>>r;
if(r>l)
{
s4=st2.get(1,1,n,l,l);
if(s4>=r)
{
cout<<"YES";
}
else cout<<"NO";
}
else
{
s4=st1.get(1,1,n,l,l);
if(s4<=r)
{
cout<<"YES";
}
else cout<<"NO";
}
cout<<"\n";
}
}
Compilation message
long_mansion.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
45 | main()
| ^~~~
long_mansion.cpp: In member function 'void IT::upd(int, int, int, int, int, int)':
long_mansion.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid=l+r>>1;
| ~^~
long_mansion.cpp: In member function 'int IT::get(int, int, int, int, int)':
long_mansion.cpp:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid=l+r>>1;
| ~^~
long_mansion.cpp: In member function 'void IT2::reset(int, int, int)':
long_mansion.cpp:98:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid=l+r>>1;
| ~^~
long_mansion.cpp: In member function 'void IT2::upd(int, int, int, int, int)':
long_mansion.cpp:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | int mid=l+r>>1;
| ~^~
long_mansion.cpp: In member function 'void IT2::upd2(int, int, int, int, int)':
long_mansion.cpp:123:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int mid=l+r>>1;
| ~^~
long_mansion.cpp: In member function 'int IT2::get2(int, int, int, int, int)':
long_mansion.cpp:132:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
132 | int mid=l+r>>1;
| ~^~
long_mansion.cpp: In member function 'int IT2::get(int, int, int, int, int)':
long_mansion.cpp:139:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
139 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
57876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
