Submission #947987

#TimeUsernameProblemLanguageResultExecution timeMemory
947987Zena_Hossam Martian DNA (BOI18_dna)C++14
100 / 100
379 ms28284 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #define ll long long using namespace std; #define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //#define ll double #define ll1 long long #define F first #define S second #define sz size() #define all(s) s.begin(),s.end() #define all1(s) s.rbegin(),s.rend() int main() { //freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout); int T=1; //cin>>T;ll oo=0; while(T--) { ll n,k,z; cin>>n>>k>>z; ll arr[n]; for(ll i=0;i<n;i++){ cin>>arr[i]; } map<ll,ll>m,d; for(ll i=0;i<z;i++){ ll a,b; cin>>a>>b; m[a]=b; }ll c=k-z;ll mn=1e18;ll o=0; for(ll i=0;i<n;i++){ d[arr[i]]++; if(d[arr[i]]==m[arr[i]])c++; while(c==k){//cout<<i<<" "<<o<<"\n"; mn=min(mn,(i-o+1));d[arr[o]]--; if(d[arr[o]]<m[arr[o]])c--; o++; } } if(mn==1e18)cout<<"impossible"; else cout<<mn; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...