Submission #599074

#TimeUsernameProblemLanguageResultExecution timeMemory
599074piOOERope (JOI17_rope)C++17
0 / 100
29 ms62964 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1000000, M = 10000000; int a[N], ans[M], cnt[M]; vector<int> g[N]; set<pair<int, int>> st; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); memset(ans, 0x3f, sizeof(ans)); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> a[i]; --a[i]; ++cnt[a[i]]; } for (int i = 0; i < m; ++i) { st.insert({cnt[i], i}); } for (int k = 0; k < 2; ++k) { for (int i = 0; i < m; ++i) { g[i].clear(); } for (int i = k; i + 1 < n; i += 2) { if (a[i] != a[i + 1]) { g[a[i]].push_back(a[i] + 1); g[a[i] + 1].push_back(a[i]); } } for (int c = 0; c < m; ++c) { int now = cnt[c]; st.erase({cnt[c], c}); cnt[c] = 0; st.insert({cnt[c], c}); for (int to : g[c]) { st.erase({cnt[to], to}); --cnt[to]; st.insert({cnt[to], to}); } ans[c] = min(ans[c], n - now - st.rbegin()->first); st.erase({cnt[c], c}); cnt[c] = now; st.insert({cnt[c], c}); for (int to : g[c]) { st.erase({cnt[to], to}); ++cnt[to]; st.insert({cnt[to], to}); } } } for (int i = 0; i < m; ++i) { cout << ans[i] << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...