/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 5e5+100, M = 1e5+10, K = 21, MX = 30;
mt19937 rng(342236234);
int rn(int l, int r){
return uniform_int_distribution<int>(l,r)(rng);
}
int n, c[N], used[N], ptr;
vector<int> A[N];
array<int, 2> a[N];
void apply(int l, int r){
for(int j = l; j <= r; ++j){
// a[j][0] = max(a[j][0], l);
a[j][1] = min(a[j][1], r);
}
}
void apply2(int l, int r){
for(int j = l; j <= r; ++j){
a[j][0] = max(a[j][0], l);
// a[j][1] = min(a[j][1], r);
}
}
void solve(){
cin >> n;
for(int i = 1; i < n; ++i){
cin >> c[i];
}
for(int i = 1; i <= n; ++i){
a[i][0] = 1, a[i][1] = n;
int x; cin >> x;
A[i].resize(x);
for(int &y: A[i]) cin >> y;
}
set<pii> S;
S.insert({0, -1});
vector<int> last_door(n + 1, -1), last_key(n + 1, -1);
c[n] = 0;
for(int i = 1; i <= n; ++i){
for(int x: A[i]){
if(last_door[x] != -1){
S.erase(pii{last_door[x], x});
}
last_door[x] = -1;
last_key[x] = i;
}
if(S.size() && i <= n){
// cerr << last_key[c[i]] << '\n';
auto it = S.upper_bound(pii{last_key[c[i]], MOD});
if(it != S.end()){
apply((*it).ff + 1, i);
while(it != S.end()){
int nxt = (next(it) == S.end() ? i : (*next(it)).ff);
apply2((*it).ff + 1, nxt);
++it;
}
}
}
last_key[c[i]] = -1;
last_door[c[i]] = i;
S.insert({i, c[i]});
}
// for(int i = 1; i <= n; ++i){
// cerr << a[i][0] << ' ' << a[i][1] << '\n';
// }
int q; cin >> q;
for(int i = 1; i <= q; ++i){
int x, y; cin >> x >> y;
if(a[x][0] <= y && a[x][1] >= y){
cout << "YES\n";
}else{
cout << "NO\n";
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
# | 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... |