Submission #642583

#TimeUsernameProblemLanguageResultExecution timeMemory
642583andreast12 Martian DNA (BOI18_dna)C++17
100 / 100
58 ms6956 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define fi first #define se second const int mod=998244353, maxn=2e5+5; ll n, k, r, a[maxn], tipe, butuh[maxn], ki, ka, mid, res, unik, cukup, cnt[maxn], x; bool penting[maxn], bisa; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k >> r; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=r; i++) { cin >> tipe >> x; penting[tipe]=true; butuh[tipe]=x; } ki=1, ka=n, res=-1; while(ki<=ka) { mid=(ki+ka)/2, bisa=false, unik=cukup=0; for(int i=0; i<k; i++) cnt[i]=0; for(int i=1; i<=n; i++) { if(i>mid) { cnt[a[i-mid]]--; if(cnt[a[i-mid]]==0) unik--; if(penting[a[i-mid]]&&(cnt[a[i-mid]]+1==butuh[a[i-mid]])) cukup--; } cnt[a[i]]++; if(cnt[a[i]]==1) unik++; if(penting[a[i]]&&(cnt[a[i]]==butuh[a[i]])) cukup++; if(cukup==r) bisa=true; // cout << i << ": " << unik << ' ' << cukup << '\n'; } if(bisa) { res=mid; ka=mid-1; } else ki=mid+1; } if(res==-1) cout << "impossible"; else cout << res; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...