#include "shoes.h"
// #include "grader.cpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
long long count_swaps(std::vector<int> s) {
int n = s.size();
map<int,vector<int>>mp;
for(int i = 0; i < n; i++)
{
mp[s[i]].push_back(i);
}
ordered_set os;
int ans = 0;
for(int i = 0; i < n; i++)
{
if(os.find(i) != os.end()) continue;
int sz = os.size();
int idx = upper_bound(mp[-s[i]].begin(), mp[-s[i]].end(), i)-mp[-s[i]].begin();
idx = mp[-s[i]][idx];
int a = sz-os.order_of_key(i), b = sz-os.order_of_key(idx);
ans += idx-i-a+b-1;
if(s[i] > 0) ans++;
os.insert(idx);
}
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... |