Submission #522237

#	Time	Username	Problem	Language	Result	Execution time	Memory
522237		blue	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	36 ms	9580 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;

#define sz(x) int(x.size())

const int mx = 100'000;

int n;
vi act(2*mx);

string s;

vi pos[2*mx];

vi occ[26];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    cin >> s;

    for(int i = 0; i < 2*n; i++)
    {
        occ[s[i] - 'a'].push_back(i);
    }


    vector<pii> pr;

    vector<int> ls, rs;
    for(int c = 0; c < 26; c++)
    {
        sort(occ[c].begin(), occ[c].end());
        // cerr << char('a'+c) << " : ";
        // for(int o: occ[c]) cerr << o << ' ';
        // cerr << '\n';
        // cerr << sz(occ[c])/2 << '\n';
        for(int i = 0; i < sz(occ[c])/2; i++)
        {
            // cerr << "i = " << i << '\n';
            // cerr << "pair = " << occ[c][i] << ' ' << occ[c][i + (sz(occ[c])/2)] << '\n';
            pr.push_back({occ[c][i], occ[c][i + (sz(occ[c])/2)]});
        }
        // cerr << "\n";
    }

    int ct = -1;

    sort(pr.begin(), pr.end());

    for(auto p: pr)
    {
        // cerr << p.first << ' ' << p.second << '\n';
        ct++;
        act[p.first] = ct;
        act[p.second] = ct+n;
    }

    vi I(2*n);
    for(int i = 0; i < 2*n; i++) I[i] = i;
    sort(I.begin(), I.end(), [] (int x, int y)
    {
        return act[x] > act[y];
    });

    ll res = 0;

    vi BIT(1 + 2*n, 0);
    for(int i:I)
    {
        for(int j = i+1 - 1; j >= 1; j -= j&-j)
            res += BIT[j];
        for(int j = i+1; j <= 2*n; j += j&-j)
            BIT[j]++;
    }


    // for(int i = 0; i < 2*n; i++) cout << act[i] << ' ';
    // cout << '\n';
    cout << res << '\n';
}

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