Submission #1152224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152224		Ahmed57	Line Town (CCO23_day1problem3)	C++20	25 / 25	170 ms	28080 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 2e18;
const int maxn = 5e5 + 5;

int a[maxn], b[maxn], id[maxn];
ll pre[maxn][2], suf[maxn][2], pre2[maxn][2], suf2[maxn][2];
vector<int> vec[2];
ll f[2], g[2];

struct BIT
{
    int c[maxn], tot;
    void add(int x, int d) { tot += d; for (; x < maxn; x += (x & -x)) c[x] += d; }
    int sum(int x) { if (!x) return 0; int ans = 0; for (; x; x -= (x & -x)) ans += c[x]; return ans; }
    int gol(int x) { return sum(x - 1); }
    int gor(int x) { return tot - sum(x); }
}bit, bit2;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = abs(a[i]), id[i] = i, bit2.add(i, 1);
    sort(id + 1, id + n + 1, [&](int x, int y) { return b[x] > b[y]; });

    f[0] = 0, f[1] = inf;
    int l = 1;
    while (l <= n)
    {
        int r = l;
        while (r < n && b[id[l]] == b[id[r + 1]]) r++;
        for (int i = l; i <= r; i++) bit2.add(id[i], -1), bit.add(id[i], 1);
        if (!b[id[l]])
        {
            ll ans = min(f[0], f[1]);
            cout << (ans == inf ? -1 : ans); return 0;
        }
        else
        {
            g[0] = g[1] = inf;
            vec[0].clear(), vec[1].clear();
            for (int i = l; i <= r; i++)
            {
                if ((a[id[i]] == b[id[i]]) ^ (id[i] & 1)) vec[0].emplace_back(id[i]);
                else vec[1].emplace_back(id[i]);
            }
            sort(vec[0].begin(), vec[0].end()), sort(vec[1].begin(), vec[1].end());
            for (int p = 0; p < 2; p++)
            {
                if (f[p] >= inf) continue;
                int q = p ^ ((n - l + 1) & 1);
                ll C = 0;
                for (int o = 0; o < 2; o++)
                {
                    pre[0][p ^ o] = pre2[0][p ^ o] = 0;
                    for (int i = 0; i < vec[p ^ o].size(); i++)
                    {
                        int x = vec[p ^ o][i];
                        pre[i + 1][p ^ o] = pre[i][p ^ o] + bit2.gol(x);
                        pre2[i + 1][p ^ o] = pre2[i][p ^ o] + abs(bit.gol(x) - 2 * i - o);
                    }

                    suf[0][q ^ o] = suf2[0][q ^ o] = 0;
                    for (int i = 0; i < vec[q ^ o].size(); i++)
                    {
                        int x = vec[q ^ o][vec[q ^ o].size() - i - 1];
                        suf[i + 1][q ^ o] = suf[i][q ^ o] + bit2.gor(x);
                        suf2[i + 1][q ^ o] = suf2[i][q ^ o] + abs(bit.gor(x) - 2 * i - o);
                    }
                }

                int nw[2] = {0, 0}, tot[2] = {(int)vec[0].size(), (int)vec[1].size()};
                for (int k = 0; k <= (r - l + 1); k++)
                {
                    int nwx = tot[0] - nw[0], nwy = tot[1] - nw[1];
                    if (nwx == nwy || nwx - nwy == (q ? -1 : 1))
                    {
                        ll C0 = pre[nw[0]][0] + pre[nw[1]][1] + suf[tot[0] - nw[0]][0] + suf[tot[1] - nw[1]][1];
                        ll C1 = pre2[nw[0]][0] + pre2[nw[1]][1] + suf2[tot[0] - nw[0]][0] + suf2[tot[1] - nw[1]][1];
                        g[p ^ (k & 1)] = min(g[p ^ (k & 1)], f[p] + C0 + C1 / 2);
                    }
                    if (k != (r - l + 1)) nw[p ^ (k & 1)]++;
                }
            }
            f[0] = g[0], f[1] = g[1];
        }
        for (int i = l; i <= r; i++) bit.add(id[i], -1);
        l = r + 1;
    }
    ll ans = min(f[0], f[1]);
    cout << (ans == inf ? -1 : ans);
    return 0;
}

• 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