This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long fen[200000];
void upd(int x,int v) {
x++;
if(x==0)return;
while(x<200000) {
fen[x]+=v;
x+=x&(-x);
}
}
long long ask(int x) {
x++;
long long sum=0;
while(x>0) {
sum+=fen[x];
x-=x&(-x);
}
return sum;
}
long long count_swaps(vector<int> s) {
int n=s.size();
map<int,deque<int>>m;
for(int i=0;i<n;i++) {
upd(i,1);
if(s[i]>0) {
m[s[i]].push_back(i);
}
}
long long ans=0;
for(int i=0;i<n;i++) {
if(s[i]<0) {
int v=-s[i];
upd(i,-1);
ans+=ask(i);
int ind=m[v].front();
m[v].pop_front();
upd(ind,-1);
ans+=ask(ind);
}
}
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... |