Submission #368186

#	Time	Username	Problem	Language	Result	Execution time	Memory
368186		Ozy	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	544 ms	152060 KiB

shoes

#include "shoes.h"
using namespace std;
#include <bits/stdc++.h>
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)

map<lli, queue<lli> > mapa;
lli BIT[200002],visitados[200002],arr[200002];
lli n,ini,a,res,k,q;

void actualiza(lli pos, lli val){
    while (pos <= 200000) {
        BIT[pos] += val;
        pos += pos&(-pos);
    }
}

lli query(lli pos) {
    lli res = 0;
    while (pos > 0) {
        res += BIT[pos];
        pos -= pos&(-pos);
    }
    return res;
}

void limpia(lli a) {

    while(visitados[mapa[a].front()] == 1) mapa[a].pop();

}

long long count_swaps(std::vector<int> s) {

    n = s.size();
    rep(i,1,n) {
        arr[i] = s[i-1];
        a = arr[i];
        mapa[a].push(i);
    }

    ini=1;
    res = 0;
    rep (i,1,n) {

        if (visitados[i] == 0) {

            visitados[i] = 1;
            actualiza(1,1);
            actualiza(i,-1);

            a = arr[i]*(-1);

            if (arr[i] < 0) {
                ini++;

                limpia(a);
                k = mapa[a].front();
                mapa[a].pop();
                visitados[k] = 1;

                q = query(k)+k;

                actualiza(1,1);
                actualiza(k,-1);

                res += q-ini;
                ini++;
            }
            else {
                limpia(a);
                k = mapa[a].front();
                mapa[a].pop();
                visitados[k] = 1;

                q = query(k)+k;

                actualiza(1,1);
                actualiza(k,-1);

                res += q-ini;
                ini+=2;

            }

        }
    }

    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15