#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int lim=1e5;
int n;
int tri[lim+10];
int seek(int x){
int res=0;
while(x<=n){
res+=tri[x];
x+=x&-x;
}
return res;
}
void upd(int x){
while(x>0){
tri[x]++;
x-=x&-x;
}
}
long long count_swaps(std::vector<int> s) {
n=s.size();
map<int,queue<int>>q;
vector<int>tan(n);
int cnt=1;
for(int i=0;i<n;i++) q[s[i]].push(i);
for(auto [x,pos]:q){
if(x>0) break;
while(pos.size()){
int cur=pos.front();
pos.pop();
int pas=q[-s[cur]].front();
q[-s[cur]].pop();
tan[cur]=cnt;
cnt++;
tan[pas]=cnt;
cnt++;
}
}
int ans=0;
for(int i=0;i<n;i++){
ans+=seek(tan[i]);
upd(tan[i]);
}
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... |