Submission #657338

#TimeUsernameProblemLanguageResultExecution timeMemory
657338teesla Martian DNA (BOI18_dna)C++14
100 / 100
102 ms4488 KiB
#include <bits/stdc++.h> using namespace std; const int maxn=2*1e5+10; const int inf=1e8; int v[maxn], nucleo[maxn], qnt[maxn]; int main(){ int n,k,r; cin >> n>> k>> r; int rest=r; int res=inf; for(int i=0; i<n; i++)cin >> v[i]; for(int i=1; i<=r; i++){ int a,b; cin >> a >> b; nucleo[a]=b; } int i=0,f=0; int y=v[i]; qnt[y]++; if(nucleo[0]!=0 and qnt[y]==nucleo[0]) rest--; while(i<n and f<n and i<=f){ if(rest==0){ res=min(res,f-i+1); int x=v[i]; qnt[x]--; if(nucleo[x]!=0 and qnt[x]==nucleo[x]-1) rest++; i++; } else{ f++; int x=v[f]; qnt[x]++; if(nucleo[x]!=0 and nucleo[x]==qnt[x]) rest--; } } if(res==inf)cout << "impossible"<<endl; else cout << res<< endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...