#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MN = 500010;
int N, Q;
int C[MN];
vector<int> A[MN], B[MN];
int L[MN], R[MN], X[MN], Y[MN];
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4 * N, -1e9);
}
void upd(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return -1e9;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return max(L, R);
}
} bit1, bit2, bit3, bit4;
vector<pii> ord;
int main() {
scanf("%d", &N);
for(int i = 0; i < N - 1; i++) {
scanf("%d", &C[i]);
C[i]--;
}
for(int i = 0; i < N; i++) {
int k; scanf("%d", &k);
A[i].resize(k);
for(int j = 0; j < k; j++) {
scanf("%d", &A[i][j]);
A[i][j]--;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < A[i].size(); j++) {
B[ A[i][j] ].push_back(i);
}
}
for(int i = 0; i < N - 1; i++) {
int s = 0, e = (int)B[ C[i] ].size() - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(B[ C[i] ][m] <= i) {
p = B[ C[i] ][m];
s = m + 1;
}
else e = m - 1;
}
L[i] = p;
}
for(int i = N - 1; i >= 1; i--) {
int s = 0, e = (int)B[ C[i - 1] ].size() - 1, p = N;
while(s <= e) {
int m = (s + e)>>1;
if(B[ C[i - 1] ][m] >= i) {
p = B[ C[i - 1] ][m];
e = m - 1;
}
else s = m + 1;
}
R[i] = p;
}
L[N - 1] = -1;
R[0] = N;
bit1.init();
bit2.init();
for(int i = 0; i < N; i++) {
ord.push_back({ R[i], i });
}
sort(ord.begin(), ord.end());
int pos = N - 1;
for(int i = N - 2; i >= 0; i--) {
while(pos >= 0 && ord[pos].first > i) {
bit1.upd(ord[pos].second, -ord[pos].second, 0, N - 1, 1);
pos--;
}
X[i] = -bit1.quer(L[i] + 1, i, 0, N - 1, 1);
}
ord.clear();
for(int i = 0; i < N; i++) {
ord.push_back({ L[i], i });
}
sort(ord.begin(), ord.end());
pos = 0;
for(int i = 0; i < N - 1; i++) {
while(pos < N && ord[pos].first < i) {
bit2.upd(ord[pos].second, ord[pos].second, 0, N - 1, 1);
pos++;
}
Y[i] = bit2.quer(i, R[i] - 1, 0, N - 1, 1);
}
bit3.init();
bit4.init();
for(int i = 0; i < N; i++) {
bit3.upd(i, -X[i], 0, N - 1, 1);
bit4.upd(i, Y[i], 0, N - 1, 1);
}
scanf("%d", &Q);
for(int i = 0; i < Q; i++) {
int x, y; scanf("%d %d", &x, &y);
x--; y--;
if(x < y) {
if(-bit3.quer(x, y - 1, 0, N - 1, 1) <= x) printf("NO\n");
else printf("YES\n");
}
else {
if(bit4.quer(y + 1, x, 0, N - 1, 1) >= x) printf("NO\n");
else printf("YES\n");
}
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < A[i].size(); j++) {
~~^~~~~~~~~~~~~
long_mansion.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
long_mansion.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &C[i]);
~~~~~^~~~~~~~~~~~~
long_mansion.cpp:50:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int k; scanf("%d", &k);
~~~~~^~~~~~~~~~
long_mansion.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i][j]);
~~~~~^~~~~~~~~~~~~~~~
long_mansion.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
long_mansion.cpp:133:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
28 ms |
24292 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
24768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
28 ms |
24292 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
24768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
636 ms |
40388 KB |
Output is correct |
| 2 |
Correct |
649 ms |
40388 KB |
Output is correct |
| 3 |
Correct |
682 ms |
40388 KB |
Output is correct |
| 4 |
Correct |
700 ms |
40392 KB |
Output is correct |
| 5 |
Correct |
689 ms |
40392 KB |
Output is correct |
| 6 |
Correct |
569 ms |
40392 KB |
Output is correct |
| 7 |
Incorrect |
567 ms |
40392 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
28 ms |
24292 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
24768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
