Submission #767733

#	Time	Username	Problem	Language	Result	Execution time	Memory
767733		drdilyor	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	13 ms	4532 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<int> t;
    Fenwick (int n) : n(n), t(n) {}
    void inc(int i, int d=1) {
        for (; i < n; i |= i+1)
            t[i] += d;
    }
    int sum(int r) {
        int s = 0;
        for (; r >= 0; r = (r&(r+1))-1)
            s += t[r];
        return s;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;

    vector<vector<int>> ix(128);
    vector cnt(128, 0);

    for (char c : s) cnt[c]++;
    for (int i = 0; i < n*2; i++)
        ix[s[i]].push_back(i);

    vector left(n*2, 0);
    for (char c = 'a'; c <= 'z'; c++) {
        assert((int)ix[c].size() == cnt[c]);
        for (int i = 0; i < cnt[c]/2; i++) {
            left[ix[c][i]] = 1;
        }
    }

    vector<vector<int>> renum(128);
    vector arr(n*2, 0);
    for (int i = 0, k = 0; i < n * 2; i++) {
        if (left[i]) {
            arr[i] = k;
            renum[s[i]].push_back(k);
            k++;
        }
    }

    for (auto& i : renum) reverse(i.begin(), i.end());
    for (int i = 0; i < n * 2; i++) {
        if (!left[i]) {
            arr[i] = n + renum[s[i]].back();
            renum[s[i]].pop_back();
        }
    }

    Fenwick tree(n*2);
    ll res = 0;
    for (int i : arr) {
        res += tree.sum(n*2-1) - tree.sum(i);
        tree.inc(i);
    }
    cout << res << endl;

    return 0;
}

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