#include "shoes.h" using namespace std; #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> typedef long long ll; 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, ll> mp; for (ll i = 0; i < 2 * n; i++) { mp[a[i]] = i; } ordered_set s; for (ll i = 0; i < 2 * n; i++) { s.insert(i); } ll res = 0; while (s.size()) { auto x = *s.begin(); ll sz = a[x]; ll other = mp[-sz]; res += s.order_of_key(other) - (sz < 0); s.erase(mp[sz]); s.erase(mp[-sz]); } return res; }