#include <cstdio>
#include <vector>
#define X first
#define Y second
#define PB push_back
using namespace std;
const int N = 5e5 + 500;
int c[N], L[N], R[N], ima[N], tL[N], tR[N], C[N];
vector < int > mogu[N];
inline void clean(int l,int r){
for(int i = l;i < r;i++){
for(int x : mogu[i])
ima[x] = 0;
}
}
inline void ubaci(int i){
for(int x : mogu[i])
ima[x] = 1;
}
inline void siri(int l,int r, int &cL, int &cR){
for(;;){
if(cL > l && ima[C[cL - 1]]){
cL--;
if(cL != l)
ubaci(cL - 1);
continue;
}
if(cR < r && ima[C[cR + 1]]){
cR++;
if(cR != r)
ubaci(cR);
continue;
}
break;
}
}
void rijesi(int l,int r){
if(l == r) return;
//printf("l = %d r = %d\n", l, r);
if(l + 1 == r){
ubaci(l);
L[l] = r, R[l] = l;
if(ima[C[l]])
L[l] = l;
if(ima[C[r]])
R[l] = r;
clean(l, r);
//printf("L[ %d ] = %d , R[ %d ] = %d\n", 3, L[3], 3, R[3]);
return;
}
int mid = (l + r) / 2;
rijesi(l, mid); rijesi(mid, r);
int cL = mid, cR = mid - 1;
if(mid - 1 >= l)
ubaci(mid - 1);
for(int ll = mid - 1;ll >= l;ll--){
if(cL > ll + 1){
ubaci(ll); cL = ll + 1;
}
siri(l, r, cL, cR);
tL[ll] = cL, tR[ll] = cR;
}
clean(l, r);
cL = mid + 1, cR = mid;
ubaci(mid);
for(int rr = mid;rr < r;rr++){
if(cR <= rr){
ubaci(rr); cR = rr;
}
siri(l, r, cL, cR);
tL[rr] = cL, tR[rr] = cR;
// printf("cL = %d cR = %d\n", cL, cR);
}
//printf("(%d %d) L[ %d ] = %d , R[ %d ] = %d\n", l, r, 3, tL[3], 3, tR[3]);
clean(l, r);
for(int i = l;i < mid;i++){
if(R[i] == mid)
L[i] = tL[max(L[i] - 1, l)], R[i] = tR[max(L[i] - 1, l)];
}
for(int i = mid;i < r;i++){
if(L[i] == mid)
L[i] = tL[R[i]], R[i] = tR[R[i]];
}
//printf("(%d %d) L[ %d ] = %d , R[ %d ] = %d\n", l, r, 3, L[3], 3, R[3]);
return;
}
int n, q;
int main(){
scanf("%d", &n);
for(int i = 1;i < n;i++)
scanf("%d", C + i);
for(int i = 0;i < n;i++){
int kol; scanf("%d", &kol);
for(;kol--;){
int x; scanf("%d", &x);
mogu[i].PB(x);
}
}
//for(int i = 0;i <= n;i++){
// printf("%d == ", C[i]);
// if(i != n){
// printf("[ ");
// for(int x : mogu[i]) printf("%d ", x);
// printf("] == ");
// }
//}
//printf("\n");
rijesi(0, n);
//for(int i = 0;i < n;i++){
// printf("i = %d interval %d %d\n", i, L[i] - 1, R[i]);
//}
scanf("%d", &q);
for(;q--;){
int x, y; scanf("%d%d", &x, &y); x--, y--;
printf((L[x] - 1 <= y && y <= R[x]) ? "YES\n" : "NO\n");
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
long_mansion.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", C + i);
~~~~~^~~~~~~~~~~~~
long_mansion.cpp:104:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int kol; scanf("%d", &kol);
~~~~~^~~~~~~~~~~~
long_mansion.cpp:106:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; scanf("%d", &x);
~~~~~^~~~~~~~~~
long_mansion.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
long_mansion.cpp:125:18: 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); x--, y--;
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
398 ms |
26872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
