#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 19;
int n, q, C[N], lf_link[N], rg_link[N], lb[N], rb[N], tmin[N << 1], tmax[N << 1];
vector<int> ls[N];
int query_min(int l, int r) {
int res = N;
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if(l & 1) res = min(tmin[l++], res);
if(r & 1) res = min(tmin[--r], res);
}
return res;
}
int query_max(int l, int r) {
int res = -1;
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if(l & 1) res = max(tmax[l++], res);
if(r & 1) res = max(tmax[--r], res);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 0; i < n-1; i++) cin >> C[i], --C[i];
for(int i = 0, sz; i < n; i++) {
cin >> sz;
vector<int> keys(sz);
for(int j = 0; j < sz; j++) {
cin >> keys[j];
--keys[j];
ls[keys[j]].push_back(i);
}
}
rg_link[0] = n;
for(int i = 1; i < n; i++) {
auto it = lower_bound(ls[C[i-1]].begin(), ls[C[i-1]].end(), i);
if(ls[C[i-1]].empty() || it == ls[C[i-1]].end()) rg_link[i] = n;
else rg_link[i] = *it;
}
lf_link[n-1] = -1;
for(int i = 0; i < n-1; i++) {
auto it = upper_bound(ls[C[i]].begin(), ls[C[i]].end(), i);
if(ls[C[i]].empty() || it == ls[C[i]].begin()) lf_link[i] = -1;
else lf_link[i] = *prev(it);
}
/* for(int type = 0; type < n; type++) { */
/* cout << "type " << type << endl; */
/* for(int i: ls[type]) cout << i << ' '; */
/* cout << endl; */
/* } */
/* for(int i = 0; i < n; i++) cout << rg_link[i] << ' '; */
/* cout << endl; */
/* for(int i = 0; i < n; i++) cout << lf_link[i] << ' '; */
/* cout << endl; */
for(int i = 0; i < n; i++) tmin[N+i] = lf_link[i];
for(int i = 0; i < n; i++) tmax[N+i] = rg_link[i];
for(int r = 0; r < n; r++) {
int s = lf_link[r] + 1, e = r;
if(e-s+1 <= 0) {
lb[r] = n;
continue;
}
while(s < e) {
int mid = s+e >> 1;
if(query_max(lf_link[r] + 1, mid) > r) e = mid;
else s = mid+1;
}
if(rg_link[s] <= r) lb[r] = n;
else lb[r] = s;
}
for(int l = 0; l < n; l++) {
int s = l, e = rg_link[l] - 1;
if(e-s+1 <= 0) {
rb[l] = -1;
continue;
}
while(s < e) {
int mid = s+e+1 >> 1;
if(query_min(mid, rg_link[l] - 1) < l) s = mid;
else e = mid-1;
}
if(lf_link[s] >= l) rb[l] = -1;
else rb[l] = s;
}
/* for(int i = 0; i < n; i++) cout << lb[i] << ' '; */
/* cout << endl; */
/* for(int i = 0; i < n; i++) cout << rb[i] << ' '; */
/* cout << endl; */
for(int i = 0; i < n; i++) tmin[N+i] = lb[i];
for(int i = 0; i < n; i++) tmax[N+i] = rb[i];
for(int i = N-1; i >= 1; i--) tmin[i] = min(tmin[i << 1], tmin[i << 1 | 1]);
for(int i = N-1; i >= 1; i--) tmax[i] = max(tmax[i << 1], tmax[i << 1 | 1]);
cin >> q;
while(q--) {
int x, y;
cin >> x >> y;
--x, --y;
if(x < y) {
int res = query_min(x, y-1);
cout << (res > x ? "YES\n" : "NO\n");
} else {
int res = query_max(y+1, x);
cout << (res < x ? "YES\n" : "NO\n");
}
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = s+e >> 1;
~^~
long_mansion.cpp:88:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = s+e+1 >> 1;
~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
341 ms |
23604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
