Submission #1013879

#TimeUsernameProblemLanguageResultExecution timeMemory
1013879SulA Martian DNA (BOI18_dna)C++17
100 / 100
24 ms4664 KiB
#include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,k,q; cin >> n >> k >> q; int a[n], target[k] = {}, frq[k] = {}; for (int& i : a) { cin >> i; frq[i]++; } while (q--) { int x, y; cin >> x >> y; target[x] = y; } for (int val = 0; val < k; val++) { if (target[val] > frq[val]) { cout << "impossible"; return 0; } else { frq[val] = 0; } } int cnt = count(target, target + k, 0); int l = 0, r = -1; int ans = n; while (++r < n) { if (++frq[a[r]] == target[a[r]]) cnt++; if (cnt == k) { while (cnt == k) { if (--frq[a[l]] < target[a[l]]) { cnt--; } l++; } ans = min(ans, r-(l-1)+1); } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...