#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
using ll = long long;
const int MAXN = (int)(5e5) + 5;
int to[MAXN];
vector<int> has[MAXN];
pair<int, int> interval[MAXN];
int maxright[MAXN];
bool cont(int l, int r, int k) {
if (has[k].size() == 0 || has[k][0] > r || has[k].back() < l || k < 0) {
return false;
}
else {
int low = 0;
int high = has[k].size()-1;
while (low < high) {
int mid = (low + high)/2;
if (has[k][mid] >= l) {
high = mid;
}
else {
low = mid+1;
}
}
int sh = high;
low = 0; high = has[k].size()-1;
while (low < high) {
int mid = (low + high+1)/2;
if (has[k][mid] <= r) {
low = mid;
}
else {
high = mid-1;
}
}
return (low - sh + 1) > 0;
}
}
int main() {
freopen("input.in", "r", stdin);
cin.tie(0);
cin.sync_with_stdio(0);
int N, Q;
cin >> N;
to[N-1] = -1;
FR(i, N-1) {
cin >> to[i];
to[i]--;
}
FR(i, N) {
int B;
cin >> B;
FR(j, B) {
int a;
cin >> a;
a--;
has[a].push_back(i);
}
}
// maxright[N-1] = N-1;
// for (int i = N-2; i >= 0; i--) {
// int u = i;
//// if (i == 1704) {
//// cout << "Wrong";
//// }
// while (cont(i, u, to[u])) {
// u = maxright[u+1];
// }
// maxright[i] = u;
//// if (maxright[i] < i) {
//// cout << "Wrong";
//// }
// }
for (int i = 0; i < N; i++) {
int l = i;
int r = i;
while (true) {
// r = maxright[r];
if (l != 0 && cont(l, r, to[l-1])) {
l = interval[l-1].first;
r = max(r, interval[l-1].second);
}
else if (r != N-1 && cont(l, r, to[r])) {
r++;
}
else {
break;
}
}
interval[i] = {l, r};
}
cin >> Q;
FR(i, Q) {
int x, y;
cin >> x >> y;
x--, y--;
// if (i == 68) {
// cout << x << '\n';
// }
if (interval[x].first <= y && y <= interval[x].second) {
cout << "YES" << '\n';
}
else cout << "NO" << '\n';
}
return 0;
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
42 | freopen("input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
52076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
52076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
52180 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
52076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
