제출 #1182087

#제출 시각아이디문제언어결과실행 시간메모리
1182087thangdz2k7Line Town (CCO23_day1problem3)C++17
25 / 25
341 ms25572 KiB
#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 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...