Submission #510859

#	Time	Username	Problem	Language	Result	Execution time	Memory
510859		KoD	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	24 ms	3244 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

struct Fenwick {
    int size;
    vector<int> data;
    Fenwick(const int n) : size(n), data(n + 1) {}
    void add(int i, const int x) {
        i += 1;
        while (i <= size) {
            data[i] += x;
            i += i & -i;
        }
    }
    int pref(int i) const {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }
    int sum(const int l, const int r) const {
        return pref(r) - pref(l);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<char> S(2 * N);
    array<vector<int>, 26> idx = {};
    for (int i = 0; i < 2 * N; ++i) {
        std::cin >> S[i];
        idx[S[i] - 'a'].push_back(i);
    }
    array<int, 26> count = {};
    array<int, 2> len = {};
    vector<int> to(2 * N), perm(N);
    long long ans = 0;
    for (int i = 0; i < 2 * N; ++i) {
        const int k = S[i] - 'a';
        const int h = idx[k].size() / 2;
        if (count[k] >= h) {
            to[i] = N + len[1];
            len[1] += 1;
            perm[to[i] - N] = to[idx[k][count[k] - h]];
        } else {
            to[i] = len[0];
            len[0] += 1;
            ans += std::abs(to[i] - i);
        }
        count[k] += 1;
    }
    Fenwick fen(N);
    for (const int x : perm) {
        ans += fen.sum(x + 1, N);
        fen.add(x, 1);
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40