Submission #526294

#TimeUsernameProblemLanguageResultExecution timeMemory
526294bebecanvas Martian DNA (BOI18_dna)C++14
0 / 100
56 ms5016 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]={0}; int arr[200005]; for(int i=0; i<n; i++){cin >> arr[i];} for(int i=0; i<k; i++){v[i]= -97874749478494;} for(int i=0; i<r; i++){ int a, b; cin >> a >> b; v[a]= b; } int s= 0; 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==r){yea= true;} for(int i=0; i<n- mid; i++){ if(count==r){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==r){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...