#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=500030;
const int mxM=500004;
const int MOD=998244353;
const ll INF=8e18;
int N, Q;
vector <int> key[mxN];
vector <int> kpos[mxN];
int C[mxN];
int l[mxN], r[mxN];
int kp[mxN];
pii qry[mxN];
pii rng[mxN];
void input(){
cin >> N;
for(int i=1;i<N;i++) cin >> C[i];
for(int i=1;i<=N;i++){
int a;
cin >> a;
while(a--){
int b;
cin >> b;
key[i].push_back(b);
}
}
cin >> Q;
for(int i=1;i<=Q;i++){
cin >> qry[i].fi >> qry[i].se;
}
}
void make_lr(){
for(int i=1;i<=N;i++){
for(int x : key[i]) kp[x]=i;
if(i==N) break;
l[i]=kp[C[i]];
}
for(int i=1;i<=N;i++) kp[i]=N+1;
for(int i=N;i>=1;i--){
for(int x : key[i]) kp[x]=i;
if(i==1) break;
r[i-1]=kp[C[i-1]];
}
}
void f(int now){
int s=now, e=now;
while(true){
if(s!=1 && r[s-1]<=e){
s--;
s=min(s, rng[s].fi);
e=max(e, rng[s].se);
continue;
}
if(e!=N && l[e]>=s){
e++;
s=min(s, rng[e].fi);
e=max(e, rng[e].se);
continue;
}
break;
}
rng[now]=pii(s, e);
}
int main()
{
gibon
input();
make_lr();
for(int i=1;i<=N;i++) rng[i]=pii(i, i);
int M=sqrt(N);
for(int i=0;i<M;i++){
int s=N;
while(s%M!=i) s--;
for(;s>=1;s-=M){
f(s);
}
}
for(int i=1;i<=Q;i++)
{
auto [a, b]=qry[i];
if(b<rng[a].fi || b>rng[a].se) cout << "NO\n";
else cout << "YES\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35416 KB |
Output is correct |
3 |
Correct |
9 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35256 KB |
Output is correct |
5 |
Correct |
9 ms |
35420 KB |
Output is correct |
6 |
Correct |
9 ms |
35416 KB |
Output is correct |
7 |
Correct |
9 ms |
35164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35416 KB |
Output is correct |
3 |
Correct |
9 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35256 KB |
Output is correct |
5 |
Correct |
9 ms |
35420 KB |
Output is correct |
6 |
Correct |
9 ms |
35416 KB |
Output is correct |
7 |
Correct |
9 ms |
35164 KB |
Output is correct |
8 |
Correct |
71 ms |
38740 KB |
Output is correct |
9 |
Correct |
76 ms |
43152 KB |
Output is correct |
10 |
Correct |
80 ms |
43604 KB |
Output is correct |
11 |
Correct |
71 ms |
43856 KB |
Output is correct |
12 |
Correct |
66 ms |
42732 KB |
Output is correct |
13 |
Correct |
68 ms |
43408 KB |
Output is correct |
14 |
Correct |
67 ms |
43476 KB |
Output is correct |
15 |
Correct |
68 ms |
43532 KB |
Output is correct |
16 |
Correct |
67 ms |
43348 KB |
Output is correct |
17 |
Correct |
65 ms |
43348 KB |
Output is correct |
18 |
Correct |
65 ms |
43348 KB |
Output is correct |
19 |
Correct |
68 ms |
43560 KB |
Output is correct |
20 |
Correct |
71 ms |
43416 KB |
Output is correct |
21 |
Correct |
66 ms |
43348 KB |
Output is correct |
22 |
Correct |
66 ms |
43280 KB |
Output is correct |
23 |
Correct |
70 ms |
43228 KB |
Output is correct |
24 |
Correct |
72 ms |
43284 KB |
Output is correct |
25 |
Correct |
69 ms |
43088 KB |
Output is correct |
26 |
Correct |
70 ms |
43292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
44792 KB |
Output is correct |
2 |
Correct |
145 ms |
52152 KB |
Output is correct |
3 |
Correct |
164 ms |
51864 KB |
Output is correct |
4 |
Correct |
136 ms |
52068 KB |
Output is correct |
5 |
Correct |
137 ms |
52052 KB |
Output is correct |
6 |
Correct |
164 ms |
50836 KB |
Output is correct |
7 |
Correct |
150 ms |
50604 KB |
Output is correct |
8 |
Correct |
152 ms |
50696 KB |
Output is correct |
9 |
Correct |
153 ms |
50564 KB |
Output is correct |
10 |
Correct |
156 ms |
50576 KB |
Output is correct |
11 |
Correct |
152 ms |
50580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35416 KB |
Output is correct |
3 |
Correct |
9 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35256 KB |
Output is correct |
5 |
Correct |
9 ms |
35420 KB |
Output is correct |
6 |
Correct |
9 ms |
35416 KB |
Output is correct |
7 |
Correct |
9 ms |
35164 KB |
Output is correct |
8 |
Correct |
71 ms |
38740 KB |
Output is correct |
9 |
Correct |
76 ms |
43152 KB |
Output is correct |
10 |
Correct |
80 ms |
43604 KB |
Output is correct |
11 |
Correct |
71 ms |
43856 KB |
Output is correct |
12 |
Correct |
66 ms |
42732 KB |
Output is correct |
13 |
Correct |
68 ms |
43408 KB |
Output is correct |
14 |
Correct |
67 ms |
43476 KB |
Output is correct |
15 |
Correct |
68 ms |
43532 KB |
Output is correct |
16 |
Correct |
67 ms |
43348 KB |
Output is correct |
17 |
Correct |
65 ms |
43348 KB |
Output is correct |
18 |
Correct |
65 ms |
43348 KB |
Output is correct |
19 |
Correct |
68 ms |
43560 KB |
Output is correct |
20 |
Correct |
71 ms |
43416 KB |
Output is correct |
21 |
Correct |
66 ms |
43348 KB |
Output is correct |
22 |
Correct |
66 ms |
43280 KB |
Output is correct |
23 |
Correct |
70 ms |
43228 KB |
Output is correct |
24 |
Correct |
72 ms |
43284 KB |
Output is correct |
25 |
Correct |
69 ms |
43088 KB |
Output is correct |
26 |
Correct |
70 ms |
43292 KB |
Output is correct |
27 |
Correct |
132 ms |
44792 KB |
Output is correct |
28 |
Correct |
145 ms |
52152 KB |
Output is correct |
29 |
Correct |
164 ms |
51864 KB |
Output is correct |
30 |
Correct |
136 ms |
52068 KB |
Output is correct |
31 |
Correct |
137 ms |
52052 KB |
Output is correct |
32 |
Correct |
164 ms |
50836 KB |
Output is correct |
33 |
Correct |
150 ms |
50604 KB |
Output is correct |
34 |
Correct |
152 ms |
50696 KB |
Output is correct |
35 |
Correct |
153 ms |
50564 KB |
Output is correct |
36 |
Correct |
156 ms |
50576 KB |
Output is correct |
37 |
Correct |
152 ms |
50580 KB |
Output is correct |
38 |
Correct |
172 ms |
65096 KB |
Output is correct |
39 |
Correct |
171 ms |
68092 KB |
Output is correct |
40 |
Correct |
164 ms |
60844 KB |
Output is correct |
41 |
Correct |
872 ms |
66592 KB |
Output is correct |
42 |
Correct |
130 ms |
51852 KB |
Output is correct |
43 |
Correct |
105 ms |
51844 KB |
Output is correct |
44 |
Correct |
144 ms |
57428 KB |
Output is correct |
45 |
Correct |
154 ms |
57572 KB |
Output is correct |
46 |
Correct |
179 ms |
57940 KB |
Output is correct |
47 |
Correct |
146 ms |
51764 KB |
Output is correct |
48 |
Correct |
161 ms |
51684 KB |
Output is correct |
49 |
Correct |
289 ms |
57432 KB |
Output is correct |
50 |
Correct |
277 ms |
57500 KB |
Output is correct |
51 |
Correct |
305 ms |
57828 KB |
Output is correct |
52 |
Correct |
156 ms |
56424 KB |
Output is correct |
53 |
Correct |
402 ms |
61416 KB |
Output is correct |
54 |
Correct |
299 ms |
66132 KB |
Output is correct |
55 |
Correct |
315 ms |
61320 KB |
Output is correct |