Submission #1278841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278841		baotoan655	Line Town (CCO23_day1problem3)	C++20	25 / 25	215 ms	28072 KiB

Main

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const long long inf = 2e18;
const int N = 5e5 + 5;

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

struct BIT {
    int bit[N], tot;
    void add(int i, int val) {
        tot += val;
        for (; i < N; i += i & -i) bit[i] += val;
    }
    int sum(int i) {
        if (!i) return 0;
        int res = 0;
        for (; i; i -= i & -i) res += bit[i];
        return res;
    }
    int go(int x) {
        return sum(x - 1);
    }
    int sus(int x) {
        return tot - sum(x);
    }
} bit, bit2;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    file("A") else file("task");
    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]]) {
            long long 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);
                long long 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.go(x);
                        pre2[i + 1][p ^ o] = pre2[i][p ^ o] + abs(bit.go(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.sus(x);
                        suf2[i + 1][q ^ o] = suf2[i][q ^ o] + abs(bit.sus(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)) {
                        long long C0 = pre[nw[0]][0] + pre[nw[1]][1] + suf[tot[0] - nw[0]][0] + suf[tot[1] - nw[1]][1];
                        long long 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;
    }
    long long ans = min(f[0], f[1]);
    cout << (ans == inf ? -1 : ans);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:5: note: in expansion of macro 'file'
   36 |     file("A") else file("task");
      |     ^~~~
Main.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:5: note: in expansion of macro 'file'
   36 |     file("A") else file("task");
      |     ^~~~
Main.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:20: note: in expansion of macro 'file'
   36 |     file("A") else file("task");
      |                    ^~~~
Main.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:20: note: in expansion of macro 'file'
   36 |     file("A") else file("task");
      |                    ^~~~

• 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