#include <bits/stdc++.h>
using namespace std;
vector<int> adj[3005];
bool cyc=false,v[3005],isdoing[3005];
void dfs(int x){
if(isdoing[x]) cyc=true;
if(v[x]) return;
v[x]=1;
isdoing[x]=1;
for(int i:adj[x]) dfs(i);
isdoing[x]=0;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,k,q;
cin >> n >> k >> q;
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
int prec[n];
for(int i=0; i<n; i++){
int lo=i,hi=n-1,mid;
while(lo<hi){
mid=(lo+hi+1)/2;
int ev=0;
for(int j=0; j<=k; j++){
adj[j].clear();
v[j]=0;
isdoing[j]=0;
}
for(int j=i+1; j<=mid; j++){
if(ev){
adj[arr[j]].push_back(arr[j-1]);
}
else{
adj[arr[j-1]].push_back(arr[j]);
}
ev^=1;
}
cyc=false;
for(int j=i; j<=mid; j++){
dfs(arr[j]);
}
//cout << i << ' ' << mid << ' ' << cyc << ' ' << found << '\n';
if(cyc){
hi=mid-1;
}
else lo=mid;
}
prec[i]=lo;
//cout << lo << ' ';
}
for(int i=0; i<q; i++){
int a,b;
cin >> a >> b;
a--; b--;
if(b<=prec[a]) cout << "YES\n";
else cout << "NO\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
3352 KB |
Output is correct |
2 |
Correct |
183 ms |
3368 KB |
Output is correct |
3 |
Correct |
187 ms |
3356 KB |
Output is correct |
4 |
Correct |
107 ms |
3280 KB |
Output is correct |
5 |
Correct |
120 ms |
3552 KB |
Output is correct |
6 |
Correct |
183 ms |
3364 KB |
Output is correct |
7 |
Correct |
185 ms |
3404 KB |
Output is correct |
8 |
Correct |
203 ms |
3372 KB |
Output is correct |
9 |
Correct |
212 ms |
3500 KB |
Output is correct |
10 |
Correct |
340 ms |
3872 KB |
Output is correct |
11 |
Correct |
575 ms |
4416 KB |
Output is correct |
12 |
Correct |
549 ms |
4288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
135 ms |
3436 KB |
Output is correct |
2 |
Correct |
132 ms |
3388 KB |
Output is correct |
3 |
Correct |
133 ms |
3404 KB |
Output is correct |
4 |
Correct |
109 ms |
4428 KB |
Output is correct |
5 |
Correct |
149 ms |
3540 KB |
Output is correct |
6 |
Correct |
131 ms |
3352 KB |
Output is correct |
7 |
Correct |
134 ms |
3436 KB |
Output is correct |
8 |
Correct |
134 ms |
3456 KB |
Output is correct |
9 |
Correct |
158 ms |
3784 KB |
Output is correct |
10 |
Correct |
151 ms |
4360 KB |
Output is correct |
11 |
Correct |
144 ms |
4552 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
377 ms |
440 KB |
Output is correct |
3 |
Correct |
455 ms |
448 KB |
Output is correct |
4 |
Correct |
44 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
329 ms |
560 KB |
Output is correct |
8 |
Correct |
594 ms |
444 KB |
Output is correct |
9 |
Correct |
850 ms |
584 KB |
Output is correct |
10 |
Correct |
902 ms |
444 KB |
Output is correct |
11 |
Execution timed out |
1014 ms |
468 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
3352 KB |
Output is correct |
2 |
Correct |
183 ms |
3368 KB |
Output is correct |
3 |
Correct |
187 ms |
3356 KB |
Output is correct |
4 |
Correct |
107 ms |
3280 KB |
Output is correct |
5 |
Correct |
120 ms |
3552 KB |
Output is correct |
6 |
Correct |
183 ms |
3364 KB |
Output is correct |
7 |
Correct |
185 ms |
3404 KB |
Output is correct |
8 |
Correct |
203 ms |
3372 KB |
Output is correct |
9 |
Correct |
212 ms |
3500 KB |
Output is correct |
10 |
Correct |
340 ms |
3872 KB |
Output is correct |
11 |
Correct |
575 ms |
4416 KB |
Output is correct |
12 |
Correct |
549 ms |
4288 KB |
Output is correct |
13 |
Correct |
135 ms |
3436 KB |
Output is correct |
14 |
Correct |
132 ms |
3388 KB |
Output is correct |
15 |
Correct |
133 ms |
3404 KB |
Output is correct |
16 |
Correct |
109 ms |
4428 KB |
Output is correct |
17 |
Correct |
149 ms |
3540 KB |
Output is correct |
18 |
Correct |
131 ms |
3352 KB |
Output is correct |
19 |
Correct |
134 ms |
3436 KB |
Output is correct |
20 |
Correct |
134 ms |
3456 KB |
Output is correct |
21 |
Correct |
158 ms |
3784 KB |
Output is correct |
22 |
Correct |
151 ms |
4360 KB |
Output is correct |
23 |
Correct |
144 ms |
4552 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
377 ms |
440 KB |
Output is correct |
27 |
Correct |
455 ms |
448 KB |
Output is correct |
28 |
Correct |
44 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
329 ms |
560 KB |
Output is correct |
32 |
Correct |
594 ms |
444 KB |
Output is correct |
33 |
Correct |
850 ms |
584 KB |
Output is correct |
34 |
Correct |
902 ms |
444 KB |
Output is correct |
35 |
Execution timed out |
1014 ms |
468 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |