Submission #1109758

#TimeUsernameProblemLanguageResultExecution timeMemory
1109758Kirill22Money (IZhO17_money)C++17
100 / 100
248 ms36356 KiB
#include "bits/stdc++.h" using namespace std; const int N = (int) 1e6 + 22; mt19937 gen(22); int p[N], mn[N]; int get(int v) { return v == p[v] ? v : p[v] = get(p[v]); } void merge(int v, int u) { v = get(v), u = get(u); mn[u] = min(mn[u], mn[v]); p[v] = u; } void solve() { iota(p, p + N, 0); iota(mn, mn + N, 0); int n = gen() % 10 + 1; cin >> n; vector<int> a(n); vector<int> cnt(N, 0), prv(N, -1); for (int i = 0; i < n; i++) { // a[i] = gen() % 10 + 1; cin >> a[i]; cnt[a[i]]++; } for (int i = 0; i + 1 < N; i++) { if (!cnt[i]) { merge(i, i + 1); } } // cout << n << endl; // for (int i = 0; i < n; i++) { // cout << a[i] << " "; // } // cout << endl; { auto b = a; std::sort(b.begin(), b.end()); for (int i = 1; i < n; i++) { if (b[i] != b[i - 1]) { prv[b[i]] = b[i - 1]; } } } int ans = 0; while (!a.empty()) { ans++; int j = (int) a.size() - 1, c = 1; bool is_first = true; while (j > 0) { // cout << j << endl; if (a[j - 1] == a[j]) { j--; c++; continue; } if (a[j - 1] != prv[a[j]]) { break; } if (is_first) { is_first = false; j--; c = 1; continue; } if (c == cnt[a[j]]) { j--; c = 1; } else { break; } } // cout << j << " " << a.size() << endl; for (int i = j; i < (int) a.size(); i++) { cnt[a[i]]--; if (cnt[a[i]] == 0) { merge(a[i], a[i] + 1); int it = get(a[i]); if (it != N - 1) { if (mn[it] == 0) { prv[it] = -1; } else { prv[it] = mn[it] - 1; } } } } while ((int) a.size() > j) { a.pop_back(); } } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...