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 <cstdio>
#include <cassert>
#include <vector>
#include <deque>
#include <cmath>
#define MAX 100005
using namespace std;
int aib[MAX];
int ub(int x)
{
return x&(-x);
}
void add(int poz)
{
for(;poz<MAX;poz+=ub(poz))
++aib[poz];
}
int sum(int poz)
{
int s=0;
for(;poz;poz-=ub(poz))
s+=aib[poz];
return s;
}
deque<int>left[MAX];
deque<int>right[MAX];
long long count_swaps(vector<int> s) {
int ind=0;
long long rasp=0;
for(auto i : s)
{
++ind;
if(i<0)
left[-i].push_back(ind);
else
right[i].push_back(ind);
int abss=abs(i);
if(!left[abss].empty() && !right[abss].empty())
{
int indd=left[abss].front();
left[abss].pop_front();
rasp+=indd-1-sum(indd-1);
add(indd);
indd=right[abss].front();
right[abss].pop_front();
rasp+=indd-1-sum(indd-1);
add(indd);
}
}
return rasp;
}
# | 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... |