Submission #1003820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003820		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	13 ms	3836 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define fr first
#define sc second

int n, bit[MAXN];
string v;
vector<int> L[26];

void update(int x, int val) {
    for( ; x <= n; x += x&-x)
        bit[x] += val;
}

int sum(int x) {
    int cnt = 0;
    while(x > 0) {
        cnt += bit[x];
        x -= x&-x;
    }
    return cnt;
}
int main() {

    cin >> n >> v;
    n *= 2;

    for(int i = 0; i < n; i++) L[v[i] - 'a'].pb(i+1);

    vector<pii> p;

    for(int i = 0; i < 26; i++)
        for(int j = 0; j < sz(L[i])/2; j++) 
            p.pb({L[i][j], L[i][j + sz(L[i])/2]});

    vector<int> flag(n+1);

    for(auto [a,b] : p) flag[a] = -1, flag[b] = a;//, cout << a << " " << b << "\n";

    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        if(flag[i] != -1) {
            update(flag[i], -1);
            ans += sum(flag[i]);
        }
        else {
            update(i, 1);
            int x = sum(i-1);
            ans += ((i-1) - x)/2; 
        }
    }

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

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