Submission #512630

#	Time	Username	Problem	Language	Result	Execution time	Memory
512630		phathnv	Ekoeko (COCI21_ekoeko)	C++11	110 / 110	22 ms	3336 KiB

Main

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

struct BIT {
    int n;
    vector<int> d;
    void init(int _n) {
        n = _n;
        d.assign(n + 1, 0);
    }
    void update(int x, int val) {
        for (; x <= n; x += x & -x) {
            d[x] += val;
        }
    }
    int get(int x) {
        int res = 0;
        for (;x > 0; x -= x & -x) {
            res += d[x];
        }
        return res;
    }
} bit;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> pos[26], newPos[26];
    for (int i = 0; i < 2 * n; ++i) {
        pos[s[i] - 'a'].push_back(i + 1);
    }
    vector<array<int, 2>> firstHalf;
    for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < (int) pos[i].size() / 2; ++j) {
            firstHalf.push_back({pos[i][j], i});
        }
    }
    sort(firstHalf.begin(), firstHalf.end());
    for (int i = 0; i < 26; ++i) {
        reverse(pos[i].begin(), pos[i].end());
    }
    bit.init(2 * n);
    long long ans = 0;
    for (int t = 0; t < 2; ++t) {
        for (auto x : firstHalf) {
            int p = pos[x[1]].back();
            //cerr << p << endl;
            pos[x[1]].pop_back();
            ans += bit.get(2 * n + 1 - p);
            bit.update(2 * n + 1 - p, 1);
        }
    }
    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