| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1144483 | zhasyn | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "shoes.h"
#include <bitst/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 100;
ll fen[N];
deque <ll> pos[N], neg[N];
void upd(int i, int delta){
for(; i < N; i |= (i + 1)){
fen[i] += delta;
}
}
ll get(ll r){
ll res = 0;
for(; r >= 0; r = (r &(r + 1)) - 1){
res += fen[r];
}
return res;
}
long long count_swaps(std::vector<int> s) {
ll ans = 0, last;
for(int i = 0; i < (int)s.size(); i++){
if(vec[i] < 0) neg[-s[i]].pb(i);
else pos[s[i]].pb(i);
upd(i, 1);
}
for(int i = 0; i < n; i++){
if(was[i]) continue;
if(s[i] < 0){
last = pos[-s[i]].front();
ans -= 2;
}
else{
last = neg[s[i]].front();
ans--;
}
pos[abs(s[i])].pop_front();
pos[abs(s[i])].pop_front();
ans += get(last);
was[last] = true;
upd(last, -1);
upd(i, -1);
}
return ans;
}
