#include "shoes.h" using namespace std; #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> typedef long long ll; #define dbg(x) cerr << #x << " = " << x << "\n"; using namespace __gnu_pbds; typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set; long long count_swaps(std::vector<int> a) { ll n = a.size() / 2; map<ll, deque<ll>> mp; for (ll i = 0; i < 2 * n; i++) { mp[a[i]].push_back(i); } ordered_set s; for (ll i = 0; i < 2 * n; i++) { s.insert(i); } ll res = 0; while (s.size()) { // dbg(s.size()); auto x = *s.begin(); ll sz = a[x]; mp[sz].pop_front(); ll other = mp[-sz].front(); mp[-sz].pop_front(); res += s.order_of_key(other) - (sz < 0); s.erase(x); s.erase(other); } return res; }