제출 #1010386

#제출 시각아이디문제언어결과실행 시간메모리
1010386uyt777443 Martian DNA (BOI18_dna)C++17
0 / 100
267 ms19276 KiB
#include <iostream> #include <iomanip> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <vector> #include <utility> #include <algorithm> #include <numeric> #include <string> #include <cmath> #include <random> #include <sstream> #include <string.h> #include <assert.h> #include <limits.h> using namespace std; #define fi first #define se second #define int long long #define pb push_back typedef pair<int,int> ii; const int INF = 1e18; map<int, int> cons; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, r; cin >> n >> k >> r; vector<int> a(n + 2); for (int i=1; i<=n; i++) cin >> a[i]; for (int i=1; i<=r; i++) { int b, q; cin >> b >> q; cons[b] = q; } // cout << "HERE\n"; queue<int> cur; map<int, int> rem; int cnt = 0; int ans = INF; map<int, int> have; for (int i=1; i<=n; i++) { // cout << ">> " << a[i] << " " << have[a[i]] << " " << cons[a[i]] << '\n'; if (cons.count(a[i]) && have[a[i]] < cons[a[i]]) { cur.push(a[i]), have[a[i]]++; if (have[a[i]] == cons[a[i]]) cnt++; } else { have[a[i]]++; cur.push(a[i]); if (cur.front() == a[i]) cur.pop(), have[a[i]]--; else rem[a[i]]++; } if (cnt == r) ans = min(ans, (int)cur.size()); while(!cur.empty() && rem[cur.front()] > 0) { rem[cur.front()]--; have[cur.front()]--; cur.pop(); } } if (ans == INF) 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...