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