# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
891626 | oolimry | Martian DNA (BOI18_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n,k,r; cin>>n>>k>>r;
int arr[n];
map<int,int>m;
map<int,int>req;
set<int>s;
for(int i=0; i<n; i++) cin>>arr[i];
for(int i=0; i<r; i++){
int a,b; cin>>a>>b;
req[a]=b;
s.insert(a);
}
int st=0,ans=LLONG_MAX;
for(int i=0; i<n; i++){
if(req.find(arr[i])!=req.end()) m[arr[i]]++;
if(m[arr[i]]>=req[arr[i]] and s.find(arr[i])!=s.end()) s.erase(arr[i]);
while(s.empty()){
ans=min(ans,i-st+1);
if(req.find(arr[st]) != req.end()){
m[arr[st]]--;
if(m[arr[st]]<req[arr[st]]) s.insert(arr[st]);
}
st++;
}
}
if(ans==LLONG_MAX) cout<<"impossible";
else cout<<ans;
return 0;
}