제출 #1190144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190144		alexdd	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	299 ms	32828 KiB

shoes

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int aib[200005],cate;
int qry(int poz)
{
    int aux=0;
    for(int i=poz;i<=cate;i+=(i&(-i)))
        aux += aib[i];
    return aux;
}
void upd(int poz, int newv)
{
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[i] += newv;
}
long long nrinv(vector<int> S)
{
    long long rez=0;
    cate = S.size();
    for(int i=0;i<S.size();i++)
    {
        rez += qry(abs(S[i]) + 1);
        upd(abs(S[i]), +1);
    }
    return rez;
}
map<int,set<int>> ofval;
bool used[200005];
long long count_swaps(std::vector<int> S)
{
    int n = S.size();
    for(int i=0;i<n;i++)
        ofval[S[i]].insert(i);
    long long rez=0;
    vector<int> newv;
    for(int i=0;i<n;i++)
    {
        if(used[i])
            continue;
        auto it = ofval[-S[i]].upper_bound(i);
        newv.push_back(i);
        newv.push_back(*it);
        used[(*it)] = used[i] = 1;
        ofval[-S[i]].erase(it);
        ofval[S[i]].erase(i);
        if(S[i] > 0)
            rez++;
    }
    rez += nrinv(newv);
    return rez;
}

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