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>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
using namespace std;
using LL = long long;
using pii = pair<int, int>;
void chmin(int &x, int a) {
x = min(x, a);
}
void chmax(int &x, int a) {
x = max(x, a);
}
#ifdef NYAOWO
int64_t LAST_TIMER = -1;
inline void timer() {
auto now = clock();
if (LAST_TIMER != -1) {
cerr << "Elapsed: "
<< (double)(now - LAST_TIMER) / CLOCKS_PER_SEC << " s\n";
} else {
cerr << fixed << setprecision(3);
}
LAST_TIMER = now;
}
#else
#define timer()
#endif
const int MAXN = 1000010;
int ans[MAXN];
int cnt1[MAXN];
int owo[MAXN];
struct Ayaya {
priority_queue<int, vector<int>, greater<int>> pq, gg;
Ayaya(int n) {
memset(owo, 0, sizeof(owo));
For(i, 1, n) pq.emplace(0);
}
void add(int i, int x) {
gg.emplace(owo[i]);
owo[i] += x;
pq.emplace(owo[i]);
}
int min() {
while(sz(gg) && pq.top() == gg.top()) {
pq.pop(); gg.pop();
}
return pq.top();
}
};
vector<int> vv[MAXN];
void solve(int n, int m, vector<pii> v2, vector<int> v1) {
timer();
memset(cnt1, 0, sizeof(cnt1));
For(i, 1, m) vv[i].clear();
Ayaya aya(m);
timer();
for(auto &i:v2) {
cnt1[i.F]++;
cnt1[i.S]++;
vv[i.F].eb(i.S);
vv[i.S].eb(i.F);
}
For(c2, 1, m) aya.add(c2, n - cnt1[c2]);
timer();
For(c1, 1, m) {
int add = 0;
for(auto &p:vv[c1]) aya.add(p, 1);
for(auto &i:v1) {
aya.add(i, -1);
add -= (i == c1);
}
aya.add(c1, INF);
chmin(ans[c1], aya.min() - cnt1[c1] + add);
aya.add(c1, -INF);
for(auto &i:v1) aya.add(i, 1);
for(auto &p:vv[c1]) aya.add(p, -1);
chmin(ans[c1], n - cnt1[c1] + add);
}
timer();
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// =^-w-^=
int n, m; cin >> n >> m;
vector<int> a(n);
for(auto &i:a) cin >> i;
For(i, 1, m) {
ans[i] = INF;
}
if(n % 2) {
For(_, 0, 1) {
vector<pii> v2;
for(int i = 1; i < n; i += 2) {
v2.eb(pii(a[i - 1], a[i]));
}
solve(n, m, v2, { a.back() });
reverse(all(a));
}
} else {
vector<pii> v2;
for(int i = 1; i < n; i += 2) {
v2.eb(pii(a[i - 1], a[i]));
}
solve(n, m, v2, {});
v2.clear();
for(int i = 2; i < n; i += 2) {
v2.eb(pii(a[i - 1], a[i]));
}
solve(n, m, v2, { a.front(), a.back() });
}
For(i, 1, m) cout << ans[i] << "\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... |