#include "shoes.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
struct BIT{
vector<ll> bit;
ll n;
BIT(){}
BIT(ll n): n(n){
bit.resize(n + 1, 0);
}
void update(ll u, ll x){
for(u; u <= n; u += (u & -u))bit[u]+=x;
}
ll get(ll u){
ll ans = 0;
for(u; u > 0; u -= (u & -u))ans += bit[u];
return ans;
}
ll get(ll l, ll r){
return get(r) - get(l-1);
}
};
vector<ll> d[200007];
vector<ll> l[200007], r[200007];
bool cmp(vector<ll> a, vector<ll> b) {
return min(a[0], a[1]) < min(b[0], b[1]);
}
ll count_swaps(vector<int> s) {
for(int i = 0; i < s.size(); i++) {
if(s[i] < 0) {
l[-s[i]].push_back(i + 1);
} else {
r[s[i]].push_back(i + 1);
}
}
ll n = s.size() / 2;
ll c = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < l[i].size(); j++) {
d[++c].push_back(r[i][j]);
d[c].push_back(l[i][j]);
}
}
sort(d + 1, d + c + 1, cmp);
BIT bit = BIT(s.size() + 1);
ll ans = 0;
for(int i = 1; i <= c; i++) {
for(int j = 1; j >= 0; j--) {
ll pos = i * 2 - j;
ll sus = d[i][j] + bit.get(d[i][j] + 1, s.size());
bit.update(d[i][j], 1);
ans += abs(sus - pos);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |