#include <bits/stdc++.h>
const int INF = 1e9;
template <class T> struct MinSegTree {
const T ID = INF;
T comb(T a, T b) {
return std::min(a, b);
}
int n;
std::vector<T> seg;
void init(int _n) {
n = _n;
seg.assign(2 * n, ID);
}
void pull(int p) {
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val) {
seg[p += n] = val;
for (p /= 2; p; p /= 2) pull(p);
}
void add(int p, T val) {
seg[p += n] += val;
for (p /= 2; p; p /= 2) pull(p);
}
T query(int l, int r) {
if (l > r) return ID;
T ra = ID, rb = ID;
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1) ra = comb(ra, seg[l++]);
if (r & 1) rb = comb(seg[--r], rb);
}
return comb(ra, rb);
}
};
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]--;
}
int q; cin >> q;
vector<array<int, 2>> queries(q);
for (int i = 0 ; i< q; i++) {
cin >> queries[i][0] >> queries[i][1];
queries[i][0]--, queries[i][1]--;
}
vector<int> ans(q);
auto solve = [&]() {
vector<int> L(n), R(n);
vector<vector<int>> loc(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i]; j++)
loc[a[i][j]].push_back(i);
L.back() = -1;
R.back() = n;
for (int i = 0; i < n - 1; i++) {
auto it = lower_bound(loc[c[i]].begin(), loc[c[i]].end(), i);
if (it == loc[c[i]].end()) R[i] = n;
else R[i] = *it;
it = upper_bound(loc[c[i]].begin(), loc[c[i]].end(), i);
if (it == loc[c[i]].begin()) L[i] = -1;
else L[i] = *prev(it);
}
vector<int> go_left(n);
for (int i = 0; i < n; i++) {
go_left[i] = n;
for (int j = i; j >= 0; j--) {
int val;
if (j) val = R[j - 1];
else val = n;
if (L[i] < j && i < val) {
go_left[i] = j;
}
}
}
MinSegTree<int> seg;
seg.init(n);
for (int i = 0; i < n; i++)
seg.upd(i, go_left[i]);
for (int i = 0; i < q; i++) {
if (queries[i][0] < queries[i][1]) {
int l = queries[i][0];
int r = queries[i][1];
if (seg.query(l, r - 1) <= l)
ans[i] = 0;
else
ans[i] = 1;
}
}
};
solve();
reverse(a.begin(), a.end());
c.pop_back();
reverse(c.begin(), c.end());
c.push_back(-1);
reverse(b.begin(), b.end());
for (int i = 0; i < q; i++) {
queries[i][0] = n - 1 - queries[i][0];
queries[i][1] = n - 1 - queries[i][1];
}
solve();
for (int i = 0; i < q; i++)
cout << (ans[i] ? "YES" : "NO") << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
25964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
