Submission #522693

#TimeUsernameProblemLanguageResultExecution timeMemory
522693bebecanvas Martian DNA (BOI18_dna)C++14
0 / 100
26 ms6724 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k, r; cin >> n >> k >> r; int a[200005]; for(int i=0; i<n; i++){cin >> a[i];} int b[200005]={0}; int c[200005]; for(int i=0; i<k; i++){c[i]=1;} for(int i=0; i<r; i++){ int q, w; cin >> q >> w; c[q]= w; } int ans= -1; int count= 0; int s= 0; int e= 0; for(int i=0; i<n; i++){ b[a[i]]++; if(b[a[i]]==c[a[i]]){count++;} if(count==k){e= i; ans= e-s+1; break;} } //cout << ans << endl; if(count==k){ //cout << b[a[s]] << " " << c[a[s]] << endl; while(e!=n){ //cout << e << endl; while(b[a[s]]>c[a[s]]){ //cout << "lol" << endl; b[a[s]]--; s++; //cout << "s " << s << endl; ans= min(ans, e-s+1); } e++; b[a[e]]++; ans= min(ans, e-s+1); } cout << ans << endl; }else{ cout << "impossible" << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...