Submission #1096105

#TimeUsernameProblemLanguageResultExecution timeMemory
1096105andrewp Martian DNA (BOI18_dna)C++14
100 / 100
26 ms4692 KiB
//Dedicated to my love, ivaziva #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using ll = int64_t; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pb push_back #define dbg(x) cerr<<#x<<": "<<x<<'\n'; #define dbga(A,l_,r_){for(int i_=l_;i_<=r_;i_++)cerr<<A[i_]<<' ';cerr<<'\n';} #define dbgv(a_){for(auto x_:a_) cerr<<x_<<' ';cerr<<'\n';} const int maxn = 2e5 + 3; int n, k, r; int a[maxn], info[maxn], f[maxn]; void Add(int x, int& cnt) { f[x]++; if (f[x] == info[x]) { cnt++; } } void Erase(int x, int& cnt) { if (f[x] == info[x]) { cnt--; } f[x]--; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); cin >> n >> k >> r; for (int i = 0; i < maxn; i++) { info[i] = -1; } for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < r; i++) { int B, Q; cin >> B >> Q; info[B] = Q; } int cnt = 0; int R = -1; int ans = maxn; for (int i = 0; i < n; i++) { while (R + 1 < n && cnt < r) { R += 1; Add(a[R], cnt); } if (cnt == r) { ans = min(ans, R - i + 1); } Erase(a[i], cnt); } if (ans > n) { cout << "impossible\n"; return 0; } cout << ans << '\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...