Submission #1182087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182087		thangdz2k7	Line Town (CCO23_day1problem3)	C++17	25 / 25	341 ms	25572 KiB

Main

#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;
}

Compilation message (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); }
      |                    ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 3 / 3
• Subtask 7: 2 / 2
• Subtask 8: 3 / 3