Submission #1025002

#TimeUsernameProblemLanguageResultExecution timeMemory
1025002phoenix Martian DNA (BOI18_dna)C++17
100 / 100
135 ms18576 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, r; cin >> n >> k >> r; int a[n]; for (int i = 0; i < n; i++) cin >> a[i]; int q[k] = {}; for (int i = 0; i < r; i++) { int b, c; cin >> b >> c; q[b] = c; } set<pair<int, int>> st; for (int i = 0; i < k; i++) { if (q[i]) st.insert({-1, i}); } vector<vector<int>> p(k); auto get = [&](int d) { return ((int)p[d].size() < q[d] ? -1 : p[d][(int)p[d].size() - q[d]]); }; int res = n + 1; for (int i = 0; i < n; i++) { if (q[a[i]]) { assert(st.count({get(a[i]), a[i]})); st.erase({get(a[i]), a[i]}); } p[a[i]].push_back(i); if (q[a[i]]) { st.insert({get(a[i]), a[i]}); } if (st.begin()->first != -1) res = min(res, i - st.begin()->first + 1); } if (res == n + 1) { cout << "impossible\n"; return 0; } cout << res << '\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...