Submission #1003847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003847		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	0 / 110	2 ms	2712 KiB

Main

#include <bits/stdc++.h>
using namespace std;
vector<int> tree;

void update(int pos, int i, int f, int idx){
    if(i == f){
        tree[pos]++;
        return;
    }
    int meio = (i+f)/2;
    if(idx <= meio) update(2*pos+1, i, meio, idx);
    else update(2*pos+2, meio+1, f, idx);
    tree[pos] = tree[2*pos+1] + tree[2*pos+2];
    return;
}

int query(int pos, int i, int f, int l, int r){
    if(l<=i and f<=r){
        return tree[pos];
    }
    int meio =(i+f)/2;
    int res = 0;
    if(l <= meio) res += query(2*pos+1, i, meio, l, r);
    if(r > meio) res += query(2*pos+2, meio+1, f, l, r);
    return res;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<vector<int>> letra(30);
    int n; cin >> n;
    tree.assign(4*(n+1), 0);

    string s; cin >> s;
    n *=2;

    for(int i=0; i<n; i++){
        int nmr = s[i] - 'a';
        letra[nmr].push_back(i);
    }
    vector<int> qnt(30,0);
    int res = 0;

    for(int i = 0; i<n/2; i++){
        int nmr = s[i] - 'a';
        int sz = letra[nmr].size();
        sz/=2;
        int posicao = letra[nmr][sz + qnt[nmr]];

        res += query(0,0,n,posicao, n);
        update(0,0,n, posicao);
        qnt[nmr]++;
    }

    cout << res << endl;
}

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