This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, c[N], last[N], le[N], ri[N], st[N], en[N];
vector < int > q[N];
inline bool check_left(int i){
return st[i] > 1 && ri[st[i] - 1] != -1 && ri[st[i] - 1] <= en[i];
}
inline bool check_right(int i){
return en[i] < n && le[en[i]] != -1 && st[i] <= le[en[i]];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
cin >> c[i];
}
for(int i = 1; i <= n; i++){
int x, y;
cin >> x;
while(x--){
cin >> y;
q[i].push_back(y);
}
}
memset(last, -1, sizeof(last));
for(int i = 1; i < n; i++){
for(int j : q[i]){
last[j] = i;
}
le[i] = last[c[i]];
}
memset(last, -1, sizeof(last));
for(int i = n - 1; i >= 1; i--){
for(int j : q[i + 1]){
last[j] = i + 1;
}
ri[i] = last[c[i]];
}
for(int i = 1; i <= n; i++){
st[i] = en[i] = i;
while(true){
if(check_left(i)){
en[i] = max(en[i], en[st[i] - 1]);
st[i] = min(st[i], st[st[i] - 1]);
}
else if(check_right(i)){
en[i] += 1;
}
else{
break;
}
}
}
cin >> m;
while(m--){
int x, y;
cin >> x >> y;
cout << (st[x] <= y && y <= en[x] ? "YES\n" : "NO\n");
}
}
# | 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... |