Submission #397586

#TimeUsernameProblemLanguageResultExecution timeMemory
397586timmyfengRope (JOI17_rope)C++17
0 / 100
15 ms23756 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000001; int color[N], tally[N], ans[N]; vector<int> pairs[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> color[i]; ++tally[color[i]]; } priority_queue<array<int, 2>> maxi; for (int i = 1; i <= m; ++i) { maxi.push({tally[i], i}); ans[i] = INT_MAX; } for (int k = 0; k < 2; ++k) { fill(pairs, pairs + m + 1, vector<int>()); for (int i = k; i + 2 <= n; i += 2) { if (color[i] != color[i + 1]) { pairs[color[i]].push_back(color[i + 1]); pairs[color[i + 1]].push_back(color[i]); } } for (int i = 1; i <= m; ++i) { int temp = tally[i]; maxi.push({0, i}); tally[i] = 0; for (auto j : pairs[i]) { maxi.push({--tally[j], j}); } while (maxi.top()[0] != tally[maxi.top()[1]]) { maxi.pop(); } ans[i] = min(ans[i], n - tally[i] - maxi.top()[0]); for (auto j : pairs[i]) { maxi.push({++tally[j], j}); } tally[i] = temp; maxi.push({tally[i], i}); } } for (int i = 1; i <= m; ++i) { cout << ans[i] << "\n"; } }
#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...