#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
#define int ll
const int N = 5e5 + 5;
int c[N], b[N], last[N];
vector<int> a[N];
int l[N], r[N];
int L[N], R[N];
int mn[N][20], mx[N][20];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for(int i=1;i<n;i++){
cin >> c[i];
}
for(int i=1;i<=n;i++){
cin >> b[i];
L[i] = 1, R[i] = n;
a[i].resize(b[i]);
for(int j=0;j<b[i];j++){
cin >> a[i][j];
}
}
for(int i=0;i<N;i++) last[i] = 0;
for(int i=1;i<=n;i++){
for(auto x : a[i]){
last[x] = i;
}
l[i] = last[c[i]];
}
for(int i=0;i<N;i++) last[i] = n + 1;
for(int i=n;i>0;i--){
r[i] = last[c[i]];
for(auto x : a[i]){
last[x] = i;
}
}
r[0] = N, l[n] = 0;
for(int i=0;i<=n;i++){
mx[i][0] = r[i]; // r[i]
mn[i][0] = l[i]; // l[i]
}
for(int j=1;j<20;j++){
for(int i=0;i + (1 << (j - 1)) <= n;i++){
mx[i][j] = max(mx[i][j-1], mx[i + (1 << (j - 1))][j-1]);
mn[i][j] = min(mn[i][j-1], mn[i + (1 << (j - 1))][j-1]);
}
}
auto get_mn = [&](int l_, int r_){
int lg = __lg(r_ - l_ + 1);
return min(mn[l_][lg], mn[r_ - (1 << lg) + 1][lg]);
};
auto get_mx = [&](int l_, int r_){
int lg = __lg(r_ - l_ + 1);
return max(mx[l_][lg], mx[r_ - (1 << lg) + 1][lg]);
};
for(int i=1;i<n;i++){
{
//~ int j = get_mn(i, r[i] - 1);
int l_ = i + 1, r_ = r[i] - 1;
while(l_ < r_){
int m = (l_ + r_ + 1) >> 1;
if(get_mn(m, r[i] - 1) <= i){
l_ = m;
} else {
r_ = m - 1;
}
}
int j = l_;
if(l_ == r_ && l[j] <= i){
for(int k=i+1;k<=j;k++){
L[k] = max(L[k], i + 1);
}
}
}
{
//~ int j = get_mx(l[i], i);
int l_ = l[i], r_ = i - 1;
while(l_ < r_){
int m = (l_ + r_ ) >> 1;
if(get_mx(l[i], m) > i){
r_ = m;
} else {
l_ = m + 1;
}
}
int j = l_;
if(l_ == r_ && i < r[j]){
for(int k=j+1;k<=i;k++){
R[k] = min(R[k], i);
}
}
}
}
int q; cin >> q;
while(q--){
int a, b; cin >> a >> b;
if(L[a] <= b && b <= R[a]){
cout<<"YES\n";
} else {
cout<<"NO\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
16852 KB |
Output is correct |
2 |
Correct |
11 ms |
17228 KB |
Output is correct |
3 |
Correct |
12 ms |
18076 KB |
Output is correct |
4 |
Correct |
10 ms |
16852 KB |
Output is correct |
5 |
Correct |
14 ms |
16852 KB |
Output is correct |
6 |
Correct |
12 ms |
16828 KB |
Output is correct |
7 |
Correct |
11 ms |
16904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
16852 KB |
Output is correct |
2 |
Correct |
11 ms |
17228 KB |
Output is correct |
3 |
Correct |
12 ms |
18076 KB |
Output is correct |
4 |
Correct |
10 ms |
16852 KB |
Output is correct |
5 |
Correct |
14 ms |
16852 KB |
Output is correct |
6 |
Correct |
12 ms |
16828 KB |
Output is correct |
7 |
Correct |
11 ms |
16904 KB |
Output is correct |
8 |
Correct |
87 ms |
18784 KB |
Output is correct |
9 |
Correct |
91 ms |
18944 KB |
Output is correct |
10 |
Correct |
88 ms |
19276 KB |
Output is correct |
11 |
Correct |
88 ms |
20208 KB |
Output is correct |
12 |
Correct |
82 ms |
18636 KB |
Output is correct |
13 |
Correct |
83 ms |
19008 KB |
Output is correct |
14 |
Correct |
91 ms |
19052 KB |
Output is correct |
15 |
Correct |
88 ms |
19128 KB |
Output is correct |
16 |
Correct |
89 ms |
19304 KB |
Output is correct |
17 |
Correct |
85 ms |
19104 KB |
Output is correct |
18 |
Correct |
88 ms |
19024 KB |
Output is correct |
19 |
Correct |
90 ms |
18972 KB |
Output is correct |
20 |
Correct |
84 ms |
19160 KB |
Output is correct |
21 |
Correct |
87 ms |
19240 KB |
Output is correct |
22 |
Correct |
88 ms |
19056 KB |
Output is correct |
23 |
Correct |
87 ms |
18864 KB |
Output is correct |
24 |
Correct |
98 ms |
18828 KB |
Output is correct |
25 |
Correct |
91 ms |
18980 KB |
Output is correct |
26 |
Correct |
87 ms |
18860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
192 ms |
58704 KB |
Output is correct |
2 |
Correct |
186 ms |
58612 KB |
Output is correct |
3 |
Correct |
182 ms |
58632 KB |
Output is correct |
4 |
Correct |
206 ms |
58580 KB |
Output is correct |
5 |
Correct |
189 ms |
58528 KB |
Output is correct |
6 |
Correct |
162 ms |
57340 KB |
Output is correct |
7 |
Correct |
166 ms |
57420 KB |
Output is correct |
8 |
Correct |
157 ms |
57528 KB |
Output is correct |
9 |
Correct |
169 ms |
57492 KB |
Output is correct |
10 |
Correct |
168 ms |
57428 KB |
Output is correct |
11 |
Correct |
163 ms |
57472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
16852 KB |
Output is correct |
2 |
Correct |
11 ms |
17228 KB |
Output is correct |
3 |
Correct |
12 ms |
18076 KB |
Output is correct |
4 |
Correct |
10 ms |
16852 KB |
Output is correct |
5 |
Correct |
14 ms |
16852 KB |
Output is correct |
6 |
Correct |
12 ms |
16828 KB |
Output is correct |
7 |
Correct |
11 ms |
16904 KB |
Output is correct |
8 |
Correct |
87 ms |
18784 KB |
Output is correct |
9 |
Correct |
91 ms |
18944 KB |
Output is correct |
10 |
Correct |
88 ms |
19276 KB |
Output is correct |
11 |
Correct |
88 ms |
20208 KB |
Output is correct |
12 |
Correct |
82 ms |
18636 KB |
Output is correct |
13 |
Correct |
83 ms |
19008 KB |
Output is correct |
14 |
Correct |
91 ms |
19052 KB |
Output is correct |
15 |
Correct |
88 ms |
19128 KB |
Output is correct |
16 |
Correct |
89 ms |
19304 KB |
Output is correct |
17 |
Correct |
85 ms |
19104 KB |
Output is correct |
18 |
Correct |
88 ms |
19024 KB |
Output is correct |
19 |
Correct |
90 ms |
18972 KB |
Output is correct |
20 |
Correct |
84 ms |
19160 KB |
Output is correct |
21 |
Correct |
87 ms |
19240 KB |
Output is correct |
22 |
Correct |
88 ms |
19056 KB |
Output is correct |
23 |
Correct |
87 ms |
18864 KB |
Output is correct |
24 |
Correct |
98 ms |
18828 KB |
Output is correct |
25 |
Correct |
91 ms |
18980 KB |
Output is correct |
26 |
Correct |
87 ms |
18860 KB |
Output is correct |
27 |
Correct |
192 ms |
58704 KB |
Output is correct |
28 |
Correct |
186 ms |
58612 KB |
Output is correct |
29 |
Correct |
182 ms |
58632 KB |
Output is correct |
30 |
Correct |
206 ms |
58580 KB |
Output is correct |
31 |
Correct |
189 ms |
58528 KB |
Output is correct |
32 |
Correct |
162 ms |
57340 KB |
Output is correct |
33 |
Correct |
166 ms |
57420 KB |
Output is correct |
34 |
Correct |
157 ms |
57528 KB |
Output is correct |
35 |
Correct |
169 ms |
57492 KB |
Output is correct |
36 |
Correct |
168 ms |
57428 KB |
Output is correct |
37 |
Correct |
163 ms |
57472 KB |
Output is correct |
38 |
Execution timed out |
3086 ms |
172768 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |