Submission #1023920

#TimeUsernameProblemLanguageResultExecution timeMemory
1023920cleptopod Martian DNA (BOI18_dna)C++17
100 / 100
181 ms13396 KiB
/** * author: tourist * created: **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k, r; cin >> n >> k >> r; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> reqs(k); for (int i = 0; i < r; i++) { int x, y; cin >> x >> y; reqs[x] = y; } multiset<int> st; for (int i = 0; i < k; i++) { st.insert(-reqs[i]); } vector<int> f(k); int j = 0, mn = n + 1; for (int i = 0; i < n; i++) { while (j < n && *st.begin() < 0) { st.erase(st.find(f[a[j]] - reqs[a[j]])); ++f[a[j]]; st.insert(f[a[j]] - reqs[a[j]]); j++; } if (*st.begin() >= 0) { mn = min(mn, j - i); } st.erase(st.find(f[a[i]] - reqs[a[i]])); --f[a[i]]; st.insert(f[a[i]] - reqs[a[i]]); } assert(mn >= 1); if (mn <= n) { cout << mn << '\n'; } else { cout << "impossible" << '\n'; } 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...