#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mx=500020;
int c[mx];
int b[mx];
vector<int>keys[mx];
int mxright[mx];
int mxleft[mx];
int n,m;
int leftt[mx];int rightt[mx];
int last[mx];
int canr(int i){
if(leftt[mxright[i]]>=mxleft[i]&&leftt[mxright[i]]!=-1&&mxright[i]<n){
return 1;
}return 0;
}int canl(int i){
if(rightt[mxleft[i]-1]<=mxright[i]&&rightt[mxleft[i]-1]!=-1&&mxleft[i]>1){
return 1;
}return 0;
}
int main()
{
cin>>n;
for(ll i=1;i<n;i++){
cin>>c[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
for(int j=0;j<b[i];j++){
ll x;
cin>>x;
keys[i].push_back(x);
}
}
memset(last ,-1 ,sizeof last);
for(int i=1;i<n;i++){
for(int j:keys[i]){
last[j]=i;
}
leftt[i]=last[c[i]];
}
memset(last ,-1 ,sizeof last);
for(int i=n-1;i>=1;i--){
for(int j:keys[i+1]){
last[j]=i+1;
}
rightt[i]=last[c[i]];
}
for(int i=1;i<=n;i++){
int myr=i;
int myl=i; mxleft[i]=i; mxright[i]=i;
while(1){
int xx=0;ll xo=0;
if(canr(i)){
xx=1;
myr++;
mxright[i]=myr;
}else if(canl(i)){
xo=1;
myl--; mxleft[i]=myl;
mxleft[i]=min(mxleft[i],mxleft[mxleft[i]]);
mxright[i]=max(mxright[i],mxright[mxleft[i]]);
}else{break;}
}
}
int q;cin>>q;
for(int i=0;i<q;i++){
int x,y;cin>>x>>y;
//cout<<mxleft[x]<<" "<<mxright[x];
cout<<(mxleft[x] <= y && y <= mxright[x] ? "YES" : "NO") << '\n';
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:64:15: warning: variable 'xx' set but not used [-Wunused-but-set-variable]
int xx=0;ll xo=0;
^~
long_mansion.cpp:64:23: warning: variable 'xo' set but not used [-Wunused-but-set-variable]
int xx=0;ll xo=0;
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
14208 KB |
Output is correct |
2 |
Correct |
29 ms |
14336 KB |
Output is correct |
3 |
Correct |
39 ms |
14464 KB |
Output is correct |
4 |
Correct |
26 ms |
14208 KB |
Output is correct |
5 |
Correct |
28 ms |
14208 KB |
Output is correct |
6 |
Correct |
27 ms |
14208 KB |
Output is correct |
7 |
Correct |
27 ms |
14208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
14208 KB |
Output is correct |
2 |
Correct |
29 ms |
14336 KB |
Output is correct |
3 |
Correct |
39 ms |
14464 KB |
Output is correct |
4 |
Correct |
26 ms |
14208 KB |
Output is correct |
5 |
Correct |
28 ms |
14208 KB |
Output is correct |
6 |
Correct |
27 ms |
14208 KB |
Output is correct |
7 |
Correct |
27 ms |
14208 KB |
Output is correct |
8 |
Correct |
1450 ms |
16464 KB |
Output is correct |
9 |
Correct |
1456 ms |
16408 KB |
Output is correct |
10 |
Correct |
1470 ms |
16760 KB |
Output is correct |
11 |
Correct |
1551 ms |
16892 KB |
Output is correct |
12 |
Correct |
1499 ms |
16620 KB |
Output is correct |
13 |
Correct |
1455 ms |
16760 KB |
Output is correct |
14 |
Correct |
1458 ms |
16664 KB |
Output is correct |
15 |
Correct |
1447 ms |
16716 KB |
Output is correct |
16 |
Correct |
1440 ms |
16888 KB |
Output is correct |
17 |
Correct |
1510 ms |
16888 KB |
Output is correct |
18 |
Correct |
1504 ms |
16760 KB |
Output is correct |
19 |
Correct |
1465 ms |
16616 KB |
Output is correct |
20 |
Correct |
1464 ms |
16888 KB |
Output is correct |
21 |
Correct |
1444 ms |
16956 KB |
Output is correct |
22 |
Correct |
1542 ms |
16760 KB |
Output is correct |
23 |
Correct |
1484 ms |
16636 KB |
Output is correct |
24 |
Correct |
1452 ms |
16504 KB |
Output is correct |
25 |
Correct |
1476 ms |
16528 KB |
Output is correct |
26 |
Correct |
1450 ms |
16440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2511 ms |
22504 KB |
Output is correct |
2 |
Execution timed out |
3076 ms |
27744 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
14208 KB |
Output is correct |
2 |
Correct |
29 ms |
14336 KB |
Output is correct |
3 |
Correct |
39 ms |
14464 KB |
Output is correct |
4 |
Correct |
26 ms |
14208 KB |
Output is correct |
5 |
Correct |
28 ms |
14208 KB |
Output is correct |
6 |
Correct |
27 ms |
14208 KB |
Output is correct |
7 |
Correct |
27 ms |
14208 KB |
Output is correct |
8 |
Correct |
1450 ms |
16464 KB |
Output is correct |
9 |
Correct |
1456 ms |
16408 KB |
Output is correct |
10 |
Correct |
1470 ms |
16760 KB |
Output is correct |
11 |
Correct |
1551 ms |
16892 KB |
Output is correct |
12 |
Correct |
1499 ms |
16620 KB |
Output is correct |
13 |
Correct |
1455 ms |
16760 KB |
Output is correct |
14 |
Correct |
1458 ms |
16664 KB |
Output is correct |
15 |
Correct |
1447 ms |
16716 KB |
Output is correct |
16 |
Correct |
1440 ms |
16888 KB |
Output is correct |
17 |
Correct |
1510 ms |
16888 KB |
Output is correct |
18 |
Correct |
1504 ms |
16760 KB |
Output is correct |
19 |
Correct |
1465 ms |
16616 KB |
Output is correct |
20 |
Correct |
1464 ms |
16888 KB |
Output is correct |
21 |
Correct |
1444 ms |
16956 KB |
Output is correct |
22 |
Correct |
1542 ms |
16760 KB |
Output is correct |
23 |
Correct |
1484 ms |
16636 KB |
Output is correct |
24 |
Correct |
1452 ms |
16504 KB |
Output is correct |
25 |
Correct |
1476 ms |
16528 KB |
Output is correct |
26 |
Correct |
1450 ms |
16440 KB |
Output is correct |
27 |
Correct |
2511 ms |
22504 KB |
Output is correct |
28 |
Execution timed out |
3076 ms |
27744 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |