#include <bits/stdc++.h>
using namespace std;
const int LIM = 5e5+1, INF = 1e9;
struct SegmentTree{
vector<int> a; int s = 1, l, r, c;
SegmentTree(vector<int> &v){
while((s+=s)<(int)size(v));
a.resize(2*s, INF);
for(int i=(int)size(v); --i>=0; ){
a[i+s-1] = v[i];
}
for(int i=s-1; --i>=0; ){
a[i] = min(a[2*i+1], a[2*i+2]);
}
}
int query(int x, int lx, int rx){
if(a[x] >= c || rx <= c) return 0;
if(rx - lx < 2) return lx;
int mx = (lx + rx) / 2;
return query(2*x+1, lx, mx) ? : query(2*x+2, mx, rx);
}
int operator()(int C){
c = C; return query(0, 0, s);
}
int rangeMin(int x, int lx, int rx){
if(r<=lx || rx<=l) return INF;
if(l<=lx && rx<=r) return a[x];
int mx = (lx + rx) / 2;
return min(rangeMin(2*x+1, lx, mx), rangeMin(2*x+2, mx, rx));
}
int rangeMin(int L, int R){
l = L, r = R + 1; return rangeMin(0, 0, s);
}
};
int n, q, c[LIM], last[LIM], l[LIM], r[LIM];
array<int, 2> b[LIM];
bool ans[LIM];
vector<int> a[LIM], rL(LIM+1), rR(LIM+1);
void flip(){
for(int i=1; i<n; ++i){
l[i] = n + 1 - l[i];
r[i] = n + 1 - r[i];
}
swap(l, r);
for(int i=1; i+i<n; ++i){
swap(l[i], l[n-i]);
swap(r[i], r[n-i]);
}
for(int i=1; i<=n; ++i){
rL[i] = n + 1 - rL[i];
rR[i] = n + 1 - rR[i];
}
swap(rL, rR);
for(int i=1; i+i<n+1; ++i){
swap(rL[i], rL[n+1-i]);
swap(rR[i], rR[n+1-i]);
}
for(int i=0; i<q; ++i){
for(int &j : b[i]) j = n + 1 - j;
}
}
void reach(vector<int> &v){
for(int i=1; i<n; ++i) v[i] = l[i];
SegmentTree st(v);
for(int i=1; i<=n; ++i) v[i] = min(n, st(i));
}
void solve(){
vector<int> z(n+1);
for(int i=1; i<n; ++i) z[i] =-r[i];
SegmentTree maxR(z);
int blocked[n+1];
blocked[1] = 1;
for(int i=2; i<n; ++i){
blocked[i] = !l[i] || -maxR.rangeMin(l[i], l[i-1]-1) > i;
blocked[i] += blocked[i-1];
}
for(int i=0; i<q; ++i){
auto [u, v] = b[i];
if(u > v) continue;
int x = rL[u], y = rR[u];
if(x != y){
bool init = !l[y] || -maxR.rangeMin(l[y], x-1) > y;
ans[i] = y >= v || !(blocked[v-1]-blocked[y] || init);
}
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i=1; i<n; ++i) cin >> c[i];
for(int i=1, j; i<=n; ++i){
cin >> j;
a[i].resize(j);
for(int &k : a[i]) cin >> k;
}
cin >> q;
for(int i=0; i<q; ++i){
cin >> b[i][0] >> b[i][1];
}
fill(last, last+n+1, 0);
for(int i=1; i<n; ++i){
for(int &j : a[i]) last[j] = i;
l[i] = last[c[i]];
}
fill(last, last+n+1, n+1);
for(int i=n; i>1; --i){
for(int &j : a[i]) last[j] = i;
r[i-1] = last[c[i-1]];
}
reach(rR);
flip();
reach(rR);
solve();
flip();
solve();
for(int i=0; i<q; ++i){
cout << (ans[i] ? "YES" : "NO") << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
24128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
24128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
311 ms |
39320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
24128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
