Submission #767726

#	Time	Username	Problem	Language	Result	Execution time	Memory
767726		drdilyor	Ekoeko (COCI21_ekoeko)	C++17	0 / 110	1 ms	468 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<int> arr(n);
    vector<vector<int>> ix(128);
    for (int i = 0; i < n; i++)
        ix[s[i]].push_back(i);
    for (auto& i : ix) reverse(i.begin(), i.end());

    for (int i = 0; i < n; i++) {
        assert(ix[s[i+n]].size());
        arr[i] = ix[s[i+n]].back();
        ix[s[i+n]].pop_back();
    }

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

    return 0;
}

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