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 ;
const int N = 2e5 + 2 ;
deque<int>pos[N];
int seg[N * 4];
void update(int p , int s , int e , int a , int v){
if(s == e){
seg[p] ++;
return ;
}
int md = (s + e) / 2 ;
if(a <= md)
update(p * 2 , s , md , a , v);
else update(p * 2 + 1 , md + 1 , e , a , v);
seg[p] = seg[p * 2] + seg[p * 2 + 1];
}
int get(int p , int s , int e , int a , int b){
if(s >= a && e <= b)
return seg[p];
if(s > b || e < a)
return 0 ;
int md = (s + e) / 2 ;
return get(p * 2 , s , md , a , b) + get(p * 2 + 1 , md + 1 , e , a , b);
}
int finish[N * 4];
long long count_swaps(vector<int> v) {
int n = v.size() / 2;
for(int i = 0 ; i < n * 2; i ++){
pos[n + v[i]].push_back(i);
}
long long ans = 0 ;
for(int i = 0 ;i < n * 2 ; i ++ ){
if(finish[i])continue ;
int ab = -v[i] , p = pos[ab + n].front();
finish[p]++;
pos[ab + n].pop_front();
pos[v[i] + n].pop_front();
int betwen = get(1 , 0 , n * 2 - 1 , i , p);
ans += p - i - 1 - betwen + (v[i] > 0 ? 1 : 0);
update(1 , 0 , n * 2 - 1 , p , 1);
}
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... |