Submission #1090135

#TimeUsernameProblemLanguageResultExecution timeMemory
1090135andrei_iorgulescu Martian DNA (BOI18_dna)C++14
100 / 100
23 ms4692 KiB
#include <bits/stdc++.h> using namespace std; int n, k, r; int a[200005]; int frmin[200005], fr[200005], cnt_bad; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> k >> r; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= r; i++) { int x, y; cin >> x >> y; frmin[x] = y; } cnt_bad = r; int dr = 0; int ans = 1e9; for (int i = 1; i <= n; i++) { while (dr < n and cnt_bad != 0) { dr++; fr[a[dr]]++; if (fr[a[dr]] == frmin[a[dr]]) cnt_bad--; } if (cnt_bad != 0) break; ans = min(ans, dr - i + 1); fr[a[i]]--; if (fr[a[i]] + 1 == frmin[a[i]]) cnt_bad++; } if (ans == (int)1e9) cout << "impossible"; else cout << ans; 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...