#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const long long inf = 1e18;
void minl(auto &a, auto b){ a = min(a, b); }
struct Fen{
vector <int> bit;
int n;
Fen(int _n){
n = _n;
bit.resize(n + 3, 0);
}
void upd(int u, int val){
++ u;
while (u <= n){
bit[u] += val;
u += (u & (-u));
}
}
int get(int u){
++ u;
int ans = 0;
while (u > 0){
ans += bit[u];
u -= (u & (-u));
}
return ans;
}
};
int n, a[N], sr[N];
void solve(){
cin >> n;
for (int i = 0; i < n; ++ i){
cin >> a[i]; sr[i] = i;
if (i & 1) a[i] *= -1;
}
sort(sr, sr + n, [&](int u, int v){
return make_pair(abs(a[u]), -u) > make_pair(abs(a[v]), -v);
});
Fen suffix(n), prefix(n), smaller(n);
for (int i = 0; i < n; ++ i) smaller.upd(i, 1);
vector <long long> dp = {0, inf};
for (int l = 0; l < n; ++ l){
if (a[sr[l]] == 0) break; int r = l;
while (r + 1 < n && abs(a[sr[l]]) == abs(a[sr[r + 1]])) ++ r;
vector <int> type[2];
vector <pair <long long, long long>> sum[2];
for (int i = l; i <= r; ++ i){
smaller.upd(sr[i], -1);
int pre = smaller.get(sr[i]);
int suf = n - 1 - r - pre;
if (a[sr[i]] < 0) type[0].push_back(sr[i]), sum[0].push_back({pre, suf});
else type[1].push_back(sr[i]), sum[1].push_back({pre, suf});
}
int sz = 0;
vector <int> sz1 = {0, 0};
for (int t : {0, 1}){
sz1[t] = type[t].size();
sz += sz1[t];
for (int i = 1; i < sz1[t]; ++ i) sum[t][i].first += sum[t][i - 1].first;
for (int i = sz1[t] - 2; i >= 0; -- i) sum[t][i].second += sum[t][i + 1].second;
}
//if (l == 0) cout << sum[0][0].first << ' ' << sum[0][0].second << endl;
vector <long long> nxt = {inf, inf};
for (int tusl : {0, 1}){
int tusr = ((n ^ l) & 1) ^ tusl;
//if (l == 0) cout << tusl << ' ' << tusr << endl;
vector <int> idx_pre(sz), idx_suf(sz);
for (int i = 0; i < sz; ++ i){
int t = (i & 1) ^ tusl;
if (i / 2 < sz1[t]) idx_pre[i] = type[t][i / 2];
t = (i & 1) ^ tusr;
if (i / 2 < sz1[t]) idx_suf[sz - 1 - i] = type[t][sz1[t] - 1 - i / 2];
}
long long inv = 0;
for (int i = sz - 1; i >= 0; -- i){
inv += suffix.get(idx_suf[i] - 1);
suffix.upd(idx_suf[i], 1);
}
//if (l == 0 && !tusl) cout << sz << endl;
for (int i = 0; i <= sz; ++ i){
vector <int> pre = {0, 0}, suf = {0, 0};
pre[tusl] = (i + 1) / 2; pre[!tusl] = i / 2;
suf[!tusr] = sz1[!tusr] - (sz - i) / 2;
suf[tusr] = sz1[tusr] - (sz - i + 1) / 2;
//if (l == 0 && !tusl) cout << inv << endl;
if (pre[0] == suf[0] && pre[1] == suf[1]){
long long all = inv;
for (int t : {0, 1}){
if (pre[t] > 0) all += sum[t][pre[t] - 1].first;
if (suf[t] < sz1[t]) all += sum[t][suf[t]].second;
}
minl(nxt[tusl ^ (i & 1)], dp[tusl] + all);
}
if (i == sz) break;
//if (!tusl && !l) cout << idx[i] << endl;
// i changes " -> " to " <- "
suffix.upd(idx_suf[i], -1);
inv -= suffix.get(idx_suf[i] - 1);
inv -= prefix.get(n - idx_suf[i] - 2);
inv += prefix.get(n - idx_pre[i] - 2);
inv += suffix.get(idx_pre[i] - 1);
prefix.upd(n - 1 - idx_pre[i], 1);
}
for (int i = 0; i < sz; ++ i) prefix.upd(n - 1 - idx_pre[i], -1);
}
dp = nxt;
//cout << dp[0] << ' ' << dp[1] << endl;
l = r;
}
long long ans = min(dp[0], dp[1]);
if (ans == inf) cout << -1;
else cout << ans;
}
int main(){
//freopen("mar.inp", "r", stdin);
//freopen("mar.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp:8:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
8 | void minl(auto &a, auto b){ a = min(a, b); }
| ^~~~
Main.cpp:8:20: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
8 | void minl(auto &a, auto b){ a = min(a, b); }
| ^~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |