This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct tree {
vector<int> t;
vector<int> a;
int n;
void turnon(int i) {
t[i + n] = a[i];
for (i += n; i > 1; i >>= 1) {
t[i >> 1] = max(t[i], t[i ^ 1]);
}
}
void turnoff(int i) {
t[i + n] = 0;
for (i += n; i > 1; i >>= 1) {
t[i >> 1] = max(t[i], t[i ^ 1]);
}
}
int get_max() {
return t[1];
}
tree(const vector<int> &a_) {
a = a_;
n = 1;
while (n < (int) a.size()) {
n <<= 1;
}
t.resize(2 * n, 0);
a.resize(n, 0);
for (int i = 0; i < n; ++i) {
t[i + n] = a[i];
}
for (int i = n - 1; i > 0; --i) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
--c[i];
}
vector<int> cnt(m, 0);
for (int i = 0; i < n; ++i) {
++cnt[c[i]];
}
vector<int> ans(m);
for (int u = 0; u < m; ++u) {
ans[u] = n - cnt[u];
}
tree t(cnt);
for (int p = 0; p < 2; ++p) {
vector<vector<int>> g(m);
for (int i = p; i + 1 < n; i += 2) {
if (c[i] != c[i + 1]) {
g[c[i]].push_back(c[i + 1]);
g[c[i + 1]].push_back(c[i]);
}
}
for (int u = 0; u < m; ++u) {
sort(begin(g[u]), end(g[u]));
vector<int> tmp;
int len = 0;
for (int i = 0; i < (int) g[u].size(); ++i) {
int v = g[u][i];
++len;
if (i == (int) g[u].size() - 1 || g[u][i + 1] != v) {
ans[u] = min(ans[u], n - cnt[u] - cnt[v] + len);
len = 0;
tmp.push_back(v);
}
}
g[u] = tmp;
for (int v : g[u]) {
t.turnoff(v);
}
t.turnoff(u);
ans[u] = min(ans[u], n - cnt[u] - t.get_max());
t.turnon(u);
for (int v : g[u]) {
t.turnon(v);
}
}
}
for (int u = 0; u < m; ++u) {
cout << ans[u] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |