| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1316882 | exoworldgd | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
ll count_swaps(vector<int>s) {
int n=s.size(),ans=0,t[n+1]={};
map<int,queue<int>>mp;
for(int i=0,x,pos;i<n;i++){
if(mp[-s[i]].empty())pos=i+1,mp[s[i]].push(pos);
else{
pos=mp[-s[i]].front(),mp[-s[i]].pop(),ans+=i;
for(int j=pos;j>0;j-=j&-j)ans-=t[j];
ans+=x<0;
}
for(;pos<=n;pos+=pos&-pos)t[pos]++;
}
return ans;
}