#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N;
int C[500005];
vector<vector<int>> A;
struct SegTree {
vector<int> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
for(i=0;i<MAX;i++) {
seg[i] = INF;
}
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = min(seg[2*i], seg[2*i+1]);
}
}
void update(int n) {
n += MAX/2;
n /= 2;
while(n) {
seg[n] = min(seg[2*n], seg[2*n+1]);
n /= 2;
}
}
void Edit(int n, int a) {
seg[n+MAX/2] = a;
update(n);
}
int sum(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return INF;
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
return min(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
}
int get_right(int s, int k) {
int e = MAX/2;
s++;
while(s+1<e) {
int mid = (s+e)/2;
if(sum(s, mid, 1, 0, MAX/2)>= k) {
s = mid;
}
else e = mid;
}
return s;
}
};
int L[500005];
int R[500005];
int prv[500005];
int nxt[500005];
int D[500005];
void init(vector<int> _C, vector<vector<int>> _A) {
N = _A.size();
A = _A;
int i, j;
for(i=0;i<N-1;i++) C[i] = _C[i] - 1;
for(i=0;i<N;i++) {
for(j=0;j<A[i].size();j++) A[i][j]--;
}
for(i=0;i<N;i++) D[i] = -1;
for(i=0;i<N;i++) {
prv[i] = (i == 0 ? -1 : D[C[i-1]]);
for(int n : A[i]) D[n] = i;
}
for(i=0;i<N;i++) D[i] = N;
for(i=N-1;i>=0;i--) {
nxt[i] = (i == N-1 ? N : D[C[i]]);
for(int n : A[i]) D[n] = i;
}
SegTree tree(N+5);
int MAX = tree.MAX;
for(i=0;i<N;i++) {
tree.seg[i+MAX/2] = prv[i];
}
tree.cons();
for(i=0;i<N;i++) {
L[i] = i;
R[i] = i;
int pL = L[i], pR = R[i];
while(true) {
if(R[i] < N-1) R[i] = tree.get_right(R[i], L[i]) - 1;
if(L[i] >= 1 && nxt[L[i]-1] <= R[i]) {
L[i] = L[L[i]-1];
}
R[i] = min(R[i], N-1);
if(pL==L[i]&&pR==R[i]) break;
pL= L[i];
pR = R[i];
}
}
}
bool isPos(int a, int b) {
a--;
b--;
return L[a]<=b&&b<=R[a];
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
int i, j;
vector<int> c(N-1);
for(i=0;i<N-1;i++) cin >> c[i];
vector<vector<int>> a(N);
for(i=0;i<N;i++) {
int sz;
cin >> sz;
a[i].resize(sz);
for(j=0;j<sz;j++) cin >> a[i][j];
}
init(c, a);
int Q;
cin >> Q;
while(Q--) {
int x, y;
cin >> x >> y;
cout << (isPos(x, y) ? "YES\n": "NO\n");
}
}
Compilation message
long_mansion.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
long_mansion.cpp:39:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = ns + ne >> 1;
| ~~~^~~~
long_mansion.cpp: In function 'void init(std::vector<int>, std::vector<std::vector<int> >)':
long_mansion.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(j=0;j<A[i].size();j++) A[i][j]--;
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
1008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
1008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
488 ms |
21496 KB |
Output is correct |
| 2 |
Incorrect |
478 ms |
21440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
1008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
