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<iostream>
#include<vector>
#include<queue>
#define DIM 100005
using namespace std;
static int n;
static int v[2 * DIM], aib[2 * DIM], ff[2 * DIM];
static queue<int> st[DIM], dr[DIM];
static void update(int x, int val){
for(; x <= n; x += (x & -x) ){
aib[x] += val;
}
}
static int query(int x){
int sum = 0;
for(; x >= 1; x -= (x & -x) ){
sum += aib[x];
}
return sum;
}
long long count_swaps(vector<int> s) {
int i;
long long sol = 0;
n = s.size();
for(i = 1; i <= n; i++){
v[i] = s[i - 1];
update(i, 1);
}
for(i = n; i >= 1; i--){
if(v[i] < 0){
if( !dr[ -v[i] ].empty() ){
ff[i] = dr[ -v[i] ].front();
dr[ -v[i] ].pop();
}
else{
st[ -v[i] ].push(i);
}
}
else{
if( !st[ v[i] ].empty() ){
ff[i] = st[ v[i] ].front();
st[ v[i] ].pop();
}
else{
dr[ v[i] ].push(i);
}
}
}
for(i = 1; i <= n; i++){
if(ff[i] != 0){
sol += query(ff[i]) - query(i) - 1;
if(v[i] > 0){
sol++;
}
update(ff[i], -1);
}
}
return sol;
}
# | 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... |