#include <bits/stdc++.h>
int main() {
using namespace std;
ios_base::sync_with_stdio(0);
int n; cin >> n;
vector<int> c(n);
c.back() = -1;
for (int i = 0; i < n - 1; i++)
cin >> c[i], c[i]--;
vector<vector<int>> a(n);
vector<int> b(n);
for (int i = 0; i < n; i++ ) {
cin >> b[i];
a[i].resize(b[i]);
for (int j = 0; j < b[i]; j++)
cin >> a[i][j], a[i][j]--;
sort(a[i].begin(), a[i].end());
}
vector<int> L(n), R(n); // how far you can go left and right with going both left and right
// first compute how far you can go right only going right
vector<vector<int>> loc(n);
for (int i = 0; i < n; i++)
for (int key : a[i])
loc[key].push_back(i);
auto get = [&](int t, int l, int r) -> int {
// gets the number of keys in the range [l, r]
// of type t
auto it2 = upper_bound(loc[t].begin(), loc[t].end(), r);
if (it2 == loc[t].begin())
return 0;
it2 = prev(it2);
auto it1 = lower_bound(loc[t].begin(), loc[t].end(), l);
return it2 - it1 + 1;
};
vector<int> go(n); // how far can you go purely to the right
for (int i = n - 1; i >= 0; i--) {
go[i] = i;
while (binary_search(a[i].begin(), a[i].end(), c[go[i]]))
go[i] = go[go[i] + 1];
}
for (int i = 0; i < n; i++) {
// first check if you can go left
if (i) {
R[i] = go[i];
L[i] = i;
if (get(c[i - 1], i, R[i])) {
L[i] = L[i - 1];
while (true) {
bool ok = false;
if (L[i] && get(c[L[i] - 1], L[i], R[i])) {
L[i] = L[L[i] - 1];
ok = true;
}
if (get(c[R[i]], L[i], R[i])) {
R[i] = go[R[i] + 1];
ok = true;
}
if (!ok)
break;
}
}
} else {
L[i] = 0;
R[i] = go[i];
}
}
int q; cin >> q;
while (q--) {
int x, y; cin >> x >> y;
x--, y--;
if (L[x] <= y && y <= R[x])
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3079 ms |
14572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
