Submission #742201

#	Time	Username	Problem	Language	Result	Execution time	Memory
742201		SamAnd	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	13 ms	3428 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n;
char a[N];

int m;
char b[N];

int u[N];

int t[N];
void ubd(int x, int y)
{
    while (x <= n * 2)
    {
        t[x] += y;
        x += (x & (-x));
    }
}

int qry(int x)
{
    int ans = 0;
    while (x)
    {
        ans += t[x];
        x -= (x & (-x));
    }
    return ans;
}

void solv()
{
    cin >> n;
    cin >> (a + 1);

    int q[26] = {};
    for (int i = 1; i <= n * 2; ++i)
    {
        q[a[i] - 'a']++;
    }
    for (int i = 0; i < 26; ++i)
        q[i] /= 2;

    for (int i = 1; i <= n * 2; ++i)
    {
        if (q[a[i] - 'a'])
        {
            b[++m] = a[i];
            --q[a[i] - 'a'];
        }
    }

    for (int i = n + 1; i <= n * 2; ++i)
    {
        b[i] = b[i - n];
    }

    vector<int> v[26];
    for (int i = 1; i <= n * 2; ++i)
    {
        v[b[i] - 'a'].push_back(i);
    }

    for (int i = n * 2; i >= 1; --i)
    {
        u[i] = v[a[i] - 'a'].back();
        v[a[i] - 'a'].pop_back();
    }

    ll ans = 0;
    for (int i = n * 2; i >= 1; --i)
    {
        ans += qry(u[i]);
        ubd(u[i], 1);
    }

    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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