#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
const int mxN = 5e5 + 1;
const int MAX = 1e9, MIN = -1e9;
pii seg[(1 << 20)];
pii a[mxN];
int corr[mxN];
vector<int> keys[mxN];
int n;
void build(int l = 1, int r = n, int idx = 1) {
if (l == r) {
seg[idx] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, (idx << 1));
build(mid + 1, r, (idx << 1) | 1);
seg[idx].ff = min(seg[(idx << 1)].ff, seg[(idx << 1) | 1].ff);
seg[idx].ss = max(seg[(idx << 1)].ss, seg[(idx << 1) | 1].ss);
}
int querymin(int tl, int tr, int l = 1, int r = n, int idx = 1) {
if (tl <= l && r <= tr) return seg[idx].ff;
int mid = (l + r) >> 1;
int res = MAX;
if (tl <= mid) res = min(res, querymin(tl, tr, l, mid, (idx << 1)));
if (tr > mid) res = min(res, querymin(tl, tr, mid + 1, r, (idx << 1) | 1));
return res;
}
int querymax(int tl, int tr, int l = 1, int r = n, int idx = 1) {
if (tl <= l && r <= tr) return seg[idx].ss;
int mid = (l + r) >> 1;
int res = MIN;
if (tl <= mid) res = max(res, querymax(tl, tr, l, mid, (idx << 1)));
if (tr > mid) res = max(res, querymax(tl, tr, mid + 1, r, (idx << 1) | 1));
return res;
}
map<pii, bool> sto;
bool recur(int x, int y) {
// cout << x << ' ' << y << endl;
if (sto.find({x, y}) != sto.end()) return sto[{x, y}];
sto[{x, y}] = false;
if (x < y) {
int req = querymin(x + 1, y);
if (x <= req) return true;
if (req == MIN) return false;
return sto[{x, y}] = recur(x, req);
} else if (x > y) {
int req = querymax(y, x - 1);
if (req <= x) return true;
if (req == MAX) return false;
return sto[{x, y}] = recur(x, req);
} else return true;
}
int occur[mxN];
void solve() {
cin >> n;
for (int i = 1; i < n; i++) cin >> corr[i];
for (int i = 1; i <= n; i++) {
int sz; cin >> sz;
keys[i].resize(sz);
for (int &x : keys[i]) cin >> x;
}
// sweep from left to right, take min of max
for (int i = 1; i <= n; i++) occur[i] = MIN;
a[1].ff = MIN;
for (int i = 1; i < n; i++) {
for (int x : keys[i]) occur[x] = i;
a[i + 1].ff = occur[corr[i]];
}
// sweep from right to left, take max of min
for (int i = 1; i <= n; i++) occur[i] = MAX;
a[n].ss = MAX;
for (int i = n; i > 1; i--) {
for (int x : keys[i]) occur[x] = i;
a[i - 1].ss = occur[corr[i - 1]];
}
// for (int i = 1; i <= n; i++) {
// cout << i << ": " << a[i].ff << ' ' << a[i].ss << endl;
// }
build();
int q; cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << (recur(x, y) ? "YES\n" : "NO\n");
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1272 ms |
70496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
