Submission #579004

#TimeUsernameProblemLanguageResultExecution timeMemory
579004ddy888 Martian DNA (BOI18_dna)C++17
0 / 100
75 ms7176 KiB
#undef _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define fi first #define si second typedef pair<int,int> pi; typedef tuple<int,int,int> ti; void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MAXN = 200010; int n, k, r; int arr[MAXN]; int req[MAXN]; int cnt[MAXN]; set<int> bases; int ans = 1e9; void remove(int i) { if (i == 0) return; if (!req[arr[i]]) return; --cnt[arr[i]]; if (cnt[arr[i]] < req[arr[i]]) bases.erase(arr[i]); } void add(int i) { if (!req[arr[i]]) return; ++cnt[arr[i]]; if (cnt[arr[i]] >= req[arr[i]]) bases.insert(arr[i]); } bool check(int i) { return (cnt[arr[i]] <= req[arr[i]]); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k >> r; for (int i = 1; i <= n; ++i) cin >> arr[i]; for (int i = 1; i <= r; ++i) { int x, y; cin >> x >> y; req[x] = y; } int l = 0; for (int i = 1; i <= n; ++i) { if ((int)bases.size() < r) add(i); if ((int)bases.size() == r) { while (l + 1 < i && !check(l + 1)) ++l; ans = min(ans, i - l + (l != 0)); } } if (ans == 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...