#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=3e5+10,M=505,OO=1e16,mod=1e9+7;
int n,k,q,req[N],a[N];
bool ok(int x){
int cnt[N]={0},vis[N]={0};
int valid=0;
for(int i=0;i<x;++i){
if(!req[a[i]]) continue;
cnt[a[i]]++;
if(cnt[a[i]]>=req[a[i]]&&!vis[a[i]]){
vis[a[i]]=1;
++valid;
}
}
if(valid==q) return 1;
for(int i=0,j=x;j<n;++i,++j){
cnt[a[i]]--;
cnt[a[j]]++;
if(req[a[i]]&&cnt[a[i]]<req[a[i]]&&vis[a[i]]){
vis[a[i]]=0;
--valid;
}
if(req[a[j]]&&cnt[a[j]]>=req[a[j]]&&!vis[a[j]]){
++valid;
vis[a[j]]=1;
}
if(valid==q) return 1;
}
return 0;
}
int bs(){
int low=0,high=n,med;
while(low<high){
med=(low+high)>>1;
if(ok(med)) high=med;
else low=med+1;
}
return low;
}
int main(){
LESSGO;
cin>>n>>k>>q;
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<q;++i){
int x,y; cin>>x>>y;
req[x]=y;
}
int len=bs();
if(ok(len)) cout<<len<<'\n';
else cout<<"impossible\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
3424 KB |
Output is correct |
| 2 |
Correct |
40 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
26 ms |
3808 KB |
Output is correct |
| 4 |
Correct |
32 ms |
3844 KB |
Output is correct |
| 5 |
Correct |
33 ms |
4536 KB |
Output is correct |
| 6 |
Correct |
33 ms |
3836 KB |
Output is correct |
| 7 |
Correct |
30 ms |
4008 KB |
Output is correct |
| 8 |
Correct |
40 ms |
4624 KB |
Output is correct |
| 9 |
Correct |
39 ms |
4412 KB |
Output is correct |
| 10 |
Correct |
49 ms |
3784 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 17 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 24 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
53 ms |
3736 KB |
Output is correct |
| 2 |
Correct |
65 ms |
3660 KB |
Output is correct |
| 3 |
Correct |
52 ms |
3660 KB |
Output is correct |
| 4 |
Correct |
19 ms |
3372 KB |
Output is correct |
| 5 |
Correct |
67 ms |
3820 KB |
Output is correct |
| 6 |
Correct |
79 ms |
4216 KB |
Output is correct |
| 7 |
Correct |
52 ms |
4428 KB |
Output is correct |
| 8 |
Correct |
70 ms |
4656 KB |
Output is correct |
| 9 |
Correct |
30 ms |
3788 KB |
Output is correct |
| 10 |
Correct |
38 ms |
3824 KB |
Output is correct |
| 11 |
Correct |
26 ms |
3776 KB |
Output is correct |
| 12 |
Correct |
32 ms |
3840 KB |
Output is correct |
| 13 |
Correct |
34 ms |
4556 KB |
Output is correct |
| 14 |
Correct |
32 ms |
3724 KB |
Output is correct |
| 15 |
Correct |
30 ms |
3944 KB |
Output is correct |
| 16 |
Correct |
40 ms |
4684 KB |
Output is correct |
| 17 |
Correct |
38 ms |
4296 KB |
Output is correct |
| 18 |
Correct |
51 ms |
3828 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2696 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 22 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 24 |
Correct |
5 ms |
2636 KB |
Output is correct |
| 25 |
Correct |
3 ms |
2628 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2620 KB |
Output is correct |
| 28 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2624 KB |
Output is correct |
| 30 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 31 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 32 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 33 |
Correct |
2 ms |
2636 KB |
Output is correct |
