# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1155574 | lucsdei10 | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "shoes.h"
#define int long long
const int MAXN = 1e6 + 10;
const int inf = 2e10;
const int MAXS = 1e5;
const int mod = 1e9 + 7;
const int zero = 0;
using namespace std;
int n;
int bit[MAXN];
map<int, queue<int>> q;
int s[MAXN];
void upd(int i, int sum){
while(i <= n*2){
bit[i] += sum;
i += (i & (-i));
}
}
int find(int i){
int sum = 0;
while(i > 0){
sum += bit[i];
i -= (i & (-i));
}
return sum;
}
int count_swaps(vector<int> S){
n = S.size()/2;
for(int i = 0; i < n*2; i++){
s[i + 1] = S[i];
}
int ans = 0;
for(int i = 1; i <= n*2; i++){
cin >> s[i];
upd(i, 1);
}
for(int i = 1; i <= n*2; i++){
q[s[i]].push(i);
}
for(int i = 1; i <= n; i++){
if(s[i] < 0){
if(find(i) - find(i - 1) == 0) continue;
int y = q[-s[i]].front();
q[s[i]].pop();
q[-s[i]].pop();
ans += find(y)- find(i + 1);
upd(y, -1);
}
else{
if(find(i) - find(i - 1) == 0) continue;
int y = q[-s[i]].front();
q[s[i]].pop();
q[-s[i]].pop();
ans += find(y) - find(i);
upd(y, -1);
}
}
return ans;
}
// int32_t main() {
// // freopen("cowtip.in", "r", stdin);
// // freopen("cowtip.out", "w", stdout);
// ios_base::sync_with_stdio(false);cin.tie(0);
// }