| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 526299 | 2022-02-14T08:15:24 Z | bebecanvas | Martian DNA (BOI18_dna) | C++14 | 0 ms | 0 KB |
#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]={0};
int arr[200005];
for(int i=0; i<n; i++){cin >> arr[i];}
for(int i=0; i<k; i++){v[i]= -97874749478494;}
for(int i=0; i<r; i++){
int a, b; cin >> a >> b;
v[a]= b;
}
int s= ;
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==r){yea= true;}
for(int i=0; i<n- mid; i++){
if(count==r){yea= true; yeaa= true; break;}
c[arr[i]]--;
if(c[arr[i]]==v[arr[i]]-1){count--;}
c[arr[i+mid]]++;
if(c[arr[i+mid]]==v[arr[i+mid]]){count++;}
}
if(count==r){yea= true; yeaa= true;}
if(yea){e= mid;}
else{s= mid+1;}
}
if(yeaa){cout << e << endl;}
else{cout << "impossible" << endl;}
}