Submission #526285

#TimeUsernameProblemLanguageResultExecution timeMemory
526285bebecanvas Martian DNA (BOI18_dna)C++14
0 / 100
35 ms6036 KiB
#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]; int arr[200005]; for(int i=0; i<n; i++){cin >> arr[i];} for(int i=0; i<=k; i++){v[i]= 1;} for(int i=0; i<r; i++){ int a, b; cin >> a >> b; v[a]= b; } int s= k; 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==k){yea= true;} for(int i=0; i<n- mid; i++){ if(count==k){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==k){yea= true; yeaa= true;} if(yea){e= mid;} else{s= mid+1;} } if(yeaa){cout << e << 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...