제출 #367627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367627		Ozy	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	312 ms	78300 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--)

#define val first
#define p second

map<lli, queue<lli> > mapa;
vector<pair<lli, lli> > inicios;
lli BIT[200002];
lli n,ini,a,res,k;

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;
}

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

    n = s.size();
    rep(i,1,n) {
        a = s[i-1];
        if (a < 0) {
            a *= -1;
            inicios.push_back({a,i});
        }
        else mapa[a].push(i);
    }

    ini=1;
    res = 0;
    for (auto act : inicios) {

        k = query(act.p) + act.p;
        res += k - ini;

        ini++;
        actualiza(act.p,-1);
        actualiza(1,1);

        a = mapa[act.val].front();
        mapa[act.val].pop();

        k = query(a) + a;
        res += k - ini;

        ini++;
        actualiza(a,-1);
        actualiza(1,1);
    }

    return res;
}

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