Submission #774628

#	Time	Username	Problem	Language	Result	Execution time	Memory
774628		Ozy	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	26 ms	6408 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 100000
//para el vector de orden
#define val first
#define id second

lli n,a,arr[MAX*2+2],res,cont,c_2,offset;
string st;
lli cant[30],n_cant[30];
vector<pll> orden;
queue<lli> p_real[30];
lli stree[MAX*4];

lli query(lli pos, lli ini, lli fin, lli l, lli r) {

    if (ini > r || fin < l) return 0;
    if (l <= ini && fin <= r) return stree[pos];

    lli mitad = (ini+fin)/2;
    lli a = query(pos*2,ini,mitad,l,r);
    lli b = query(pos*2+1,mitad+1,fin,l,r);
    return a+b;
}

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

    cin >> n >> st;
    rep(i,1,2*n) {
        a = st[i-1] - 'a';
        arr[i] = a;
        cant[a]++;
    }

    //dividir en 2 mitades sumar lo que le corresponde al resultado
    cont = 1;
    c_2 = 1;
    rep(i,1,n*2) {
        n_cant[arr[i]]++;
        if (n_cant[arr[i]] <= cant[arr[i]]/2) {

            p_real[arr[i]].push(cont);
            res += i - cont;
            cont++;
        }
        else {
            //debug(i);

            orden.push_back({p_real[arr[i]].front(), c_2});
            p_real[arr[i]].pop();
            c_2++;
        }
    }

    //procesar el vector de orden y actualizar el stree
    sort(orden.begin(), orden.end());

    offset = 1;
    while (offset < n) offset *= 2;
    for(auto act : orden) {
        res += query(1,1,offset,act.id,offset);
        a = offset+act.id-1;
        while(a != 0) {
            stree[a]++;
            a/=2;
        }
    }

    cout << res;

    return 0;
}

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