#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;//500009;
int N, last[NMAX], lft[NMAX], rgt[NMAX], C[NMAX], minL[NMAX], maxR[NMAX];
vector < int > v[NMAX];
void read ()
{
scanf ("%d", &N);
for (int i=1; i<N; i++)
scanf ("%d", &C[i]);
for (int i=1; i<=N; i++)
{
int l, x;
scanf ("%d", &l);
while (l --)
scanf ("%d", &x),
v[i].push_back (x),
last[x] = i;
if (i < N)
lft[i] = last[C[i]];
}
for (int i=1; i<=N; i++)
last[i] = 0;
for (int i=N; i>=2; i--)
{
for (auto it : v[i])
last[it] = i;
if (last[C[i - 1]] == 0) rgt[i - 1] = N + 1;
else rgt[i - 1] = last[C[i - 1]];
}
}
namespace segtree {
int ma[4 * NMAX], aintVal[NMAX];
void build (int nod, int st, int dr)
{
if (st == dr)
{
ma[nod] = aintVal[st];
return ;
}
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
build (f1, st, mij);
build (f2, mij + 1, dr);
ma[nod] = max (ma[f1], ma[f2]);
}
int firstBigger (int nod, int st, int dr, int x, int y, int minVal)
{
if (x > y) return -1;
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
if (x <= st && dr <= y)
{
if (ma[nod] <= minVal) return -1;
if (st == dr) return st;
if (ma[f1] > minVal) return firstBigger (f1, st, mij, x, y, minVal);
return firstBigger (f2, mij + 1, dr, x, y, minVal);
}
if (x <= mij)
{
int curr = firstBigger (f1, st, mij, x, y, minVal);
if (curr != -1) return curr;
}
if (mij < y)
return firstBigger (f2, mij + 1, dr, x, y, minVal);
return -1;
}
};
void buildMinL ()
{
for (int i=1; i<=N; i++)
segtree::aintVal[i] = (i == 1 ? N + 1 : rgt[i - 1]);
segtree::build (1, 1, N);
for (int i=1; i<=N; i++)
{
minL[i] = segtree::firstBigger (1, 1, N, lft[i] + 1, i, i);
if (minL[i] == -1)
minL[i] = N + 1;
}
}
void buildMaxR ()
{
for (int i=1; i<=N; i++)
segtree::aintVal[i] = -(i == N ? 0 : lft[i]);
reverse (segtree::aintVal + 1, segtree::aintVal + N + 1);
segtree::build (1, 1, N);
for (int i=1; i<=N; i++)
{
int lEnd = i, rEnd = rgt[i - 1] - 1;
maxR[i] = segtree::firstBigger (1, 1, N, N + 1 - rEnd, N + 1 - lEnd, -i);
if (maxR[i] == -1) maxR[i] = 0;
else maxR[i] = N + 1 - maxR[i];
}
}
void processQueries ()
{
int Q;
scanf ("%d", &Q);
while (Q --)
{
int x, y;
scanf ("%d %d", &x, &y);
bool ans = 1;
if (x < y)
{
for (int i=x; i<y; i++)
if (minL[i] <= x)
ans = 0;
}
else
{
for (int i=y + 1; i<=x; i++)
if (maxR[i] >= x)
ans = 0;
}
if (ans) printf ("YES\n");
else printf ("NO\n");
}
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
read ();
buildMinL ();
buildMaxR ();
processQueries ();
return 0;
}
Compilation message
long_mansion.cpp: In function 'void read()':
long_mansion.cpp:11:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
long_mansion.cpp:13:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &C[i]);
~~~~~~^~~~~~~~~~~~~
long_mansion.cpp:17:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &l);
~~~~~~^~~~~~~~~~
long_mansion.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &x),
~~~~~~~~~~~~~~~~~~
v[i].push_back (x),
~~~~~~~~~~~~~~~~~~^~
last[x] = i;
~~~~~~~~~~~
long_mansion.cpp: In function 'void processQueries()':
long_mansion.cpp:105:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &Q);
~~~~~~^~~~~~~~~~
long_mansion.cpp:109:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &x, &y);
~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
