#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;
bool type; // 0 : ma, 1 : mi
SegTree(int N, bool c) {
type = c;
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
for(i=0;i<MAX;i++) {
seg[i] = (c?INF:-INF);
}
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = (type ? min(seg[2*i], seg[2*i+1]) : max(seg[2*i], seg[2*i+1]));
}
}
void update(int n) {
n += MAX/2;
n /= 2;
while(n) {
seg[n] = (type ? min(seg[2*n], seg[2*n+1]) : max(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 (type ? INF : -INF);
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
int v1 = sum(s, e, 2*n, ns, mid);
int v2 = sum(s, e, 2*n+1, mid, ne);
return (type ? min(v1,v2) : max(v1,v2));
}
};
struct SegTree2 {
vector<int> seg;
int MAX;
SegTree2(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = seg[2*i] | seg[2*i+1];
}
}
void update(int n) {
n += MAX/2;
n /= 2;
while(n) {
seg[n] = 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 0;
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
int v1 = sum(s, e, 2*n, ns, mid);
int v2 = sum(s, e, 2*n+1, mid, ne);
return v1|v2;
}
};
int L[500005];
int R[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]--;
}
SegTree2 tree3(N), tree4(N);
int MAX = tree3.MAX;
for(i=0;i<N;i++) {
int s = 0;
for(int n : A[i]) s += (1<<n);
tree3.seg[i+MAX/2] = s;
}
for(i=1;i<N;i++) {
tree4.seg[i+MAX/2] = (1<<C[i-1]);
}
tree3.cons();
tree4.cons();
for(i=0;i<N;i++) {
L[i] = i;
R[i] = i;
int S = 0;
for(int n : A[i]) S += (1<<n);
if(i&& ( (1<<(C[i-1]))&S) == (1<<(C[i-1])) ) {
if(R[i-1] >= i) {
R[i] = R[i-1];
L[i] = L[i-1];
continue;
}
L[i] = min(L[i-1], L[i]);
}
S |= tree3.sum(L[i], i+1, 1, 0, MAX/2);
int pL = L[i], pR = R[i];
while(true) {
while(L[i] && ( (1<<(C[L[i]-1]))&S) == (1<<(C[L[i]-1])) ) {
L[i] = min(L[i]-1, L[L[i]-1]);
S |= tree3.sum(L[i], R[i]+1, 1, 0, MAX/2);
}
int s = R[i], e = N;
while(s+1<e) {
int mid = (s+e)/2;
int L = tree4.sum(R[i]+1, mid+1, 1, 0, MAX/2);
if((L&S)==L) {
s = mid;
}
else e = mid;
}
S |= tree3.sum(R[i], s+1, 1, 0, MAX/2);
R[i] = s;
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:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = ns + ne >> 1;
| ~~~^~~~
long_mansion.cpp: In member function 'int SegTree2::sum(int, int, int, int, int)':
long_mansion.cpp:76:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = ns + ne >> 1;
| ~~~^~~~
long_mansion.cpp: In function 'void init(std::vector<int>, std::vector<std::vector<int> >)':
long_mansion.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(j=0;j<A[i].size();j++) A[i][j]--;
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
7 ms |
852 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1372 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
7 ms |
852 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1372 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
23524 KB |
Output is correct |
| 2 |
Correct |
434 ms |
25176 KB |
Output is correct |
| 3 |
Correct |
362 ms |
24800 KB |
Output is correct |
| 4 |
Correct |
387 ms |
25280 KB |
Output is correct |
| 5 |
Correct |
403 ms |
25284 KB |
Output is correct |
| 6 |
Correct |
340 ms |
24168 KB |
Output is correct |
| 7 |
Correct |
218 ms |
24064 KB |
Output is correct |
| 8 |
Correct |
178 ms |
24012 KB |
Output is correct |
| 9 |
Correct |
186 ms |
24076 KB |
Output is correct |
| 10 |
Correct |
146 ms |
24004 KB |
Output is correct |
| 11 |
Correct |
172 ms |
23968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
7 ms |
852 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1372 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
