Submission #816291

#	Time	Username	Problem	Language	Result	Execution time	Memory
816291		andecaandeci	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	36 ms	4152 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

int cnt[50], a[N], st[4 * N];
vector<int> v1, v2, pos[50];

void update(int x, int tl, int tr, int idx) {
    //cout << x << " " << tl << " " << tr << " " << idx << "faw\n";
    if (tl == tr) st[x]++;
    else {
        int tm = (tl + tr) / 2;
        if (idx <= tm) update(2 * x, tl, tm, idx);
        else update(2 * x + 1, tm + 1, tr, idx);
        st[x]++;
    }
}

int get(int x, int tl, int tr, int l, int r) {
    if (l > r or tr < l or r < tl) return 0;
    if (l <= tl and tr <= r) return st[x];
    int tm = (tl + tr) / 2;
    return get(2 * x, tl, tm, l, r) + get(2 * x + 1, tm + 1, tr, l, r);
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; 
    ll ans = 0;
    string s, t1 = "", t2 = "";
    cin >> n >> s;
    for (int i = 0; i < 2 * n; i++) pos[s[i] - 'a'].push_back(i);
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < (int)pos[i].size() / 2; j++) v1.push_back(pos[i][j]);
    }
    sort(v1.begin(), v1.end());
    for (auto x : v1) t1 += s[x];
    for (int i = 0; i < n; i++) {
        pos[t1[i] - 'a'][cnt[t1[i] - 'a']] = i;
        cnt[t1[i] - 'a']++;
    }
    for (int i = 0; i < n; i++) ans += v1[i] - i;
    for (int i = 0; i < 26; i++) {
        for (int j = (int)pos[i].size() / 2; j < (int)pos[i].size(); j++) v2.push_back(pos[i][j]);
    }
    sort(v2.begin(), v2.end());
    for (auto x : v2) t2 += s[x];
    for (int i = 0; i < n; i++) {
        a[i] = pos[t2[i] - 'a'][cnt[t2[i] - 'a'] - (int)pos[t2[i] - 'a'].size() / 2];
        cnt[t2[i] - 'a']++;
        //cout << t2[i] << " " << a[i] << " " << "flpawkq\n";
        ans += get(1, 0, n - 1, a[i] + 1, n - 1);
        update(1, 0, n - 1, a[i]);
    }
    cout << ans << "\n";
}  

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