Submission #523374

#	Time	Username	Problem	Language	Result	Execution time	Memory
523374		HappyPacMan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	363 ms	25860 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 15;
int BIT[MAXN];

void upd(int u){
    u+=5;
    for(;u<MAXN;u+=u&(-u)) BIT[u]++;
}
int qry(int u){
    u+=5;
    int rt = 0;
    for(;u>0;u-=u&(-u)) rt += BIT[u];
    return rt;
}

long long count_swaps(std::vector<int> s) {
    map<int,vector<int> > mp;
    int N = s.size();
    for(int i=N-1;i>=0;i--){
        mp[s[i]].push_back(i);
    }
    long long res = 0;
    for(int i=0;i<N;i++){
        if(qry(i)-qry(i-1) == 1) continue;
        int ref = mp[-s[i]].back();
        mp[-s[i]].pop_back();
        if(s[i] > 0) res += ref-qry(ref-1)+qry(i)-i;
        else res += ref-qry(ref-1)+qry(i)-i-1;
        mp[s[i]].pop_back();
        upd(i);
        upd(ref);
    }
    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