#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define sz(x) (int) (x).size()
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k, r; cin >> n >> k >> r;
int v[200005];
int arr[200005];
for(int i=0; i<n; i++){cin >> arr[i];}
for(int i=0; i<=k; i++){v[i]= 1;}
for(int i=0; i<r; i++){
int a, b; cin >> a >> b;
v[a]= b;
}
int s= 1;
int e= n;
bool yeaa= false;
while(s<e){
int mid= s+ (e-s)/2;
int c[200005]={0};
int count= 0;
for(int i=0; i<mid; i++){
c[arr[i]]++;
if(c[arr[i]]==v[arr[i]]){count++;}
}
bool yea= false;
if(count==k){yea= true;}
for(int i=0; i<n- mid; i++){
if(count==k){yea= true; yeaa= true; break;}
c[arr[i]]--;
if(c[arr[i]]==v[arr[i]]){count++;}
if(c[arr[i]]==v[arr[i]]-1){count--;}
c[arr[i+mid]]++;
if(c[arr[i+mid]]==v[arr[i+mid]]-1){count++;}
if(c[arr[i+mid]]==v[arr[i+mid]]-1){count--;}
}
if(count==k){yea= true; yeaa= true;}
if(yea){e= mid;}
else{s= mid+1;}
}
if(yeaa){cout << e << endl;}
else{cout << "impossible" << endl;}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
6676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
