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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+45;
ll n,a[N];
ll drvo[5*N],sled[5*N];
void build(int i,int j,int node){
if(i == j){
drvo[node] = 1;
return;
}
int mid = i+(j-i)/2;
build(i,mid,2*node);
build(mid+1,j,2*node+1);
drvo[node] = drvo[2*node]+drvo[2*node+1];
}
void update(int i,int j,int pos,int node){
if(i == j){
drvo[node] = 0;
return;
}
int mid = i+(j-i)/2;
if(pos <= mid){
update(i,mid,pos,2*node);
}
else{
update(mid+1,j,pos,2*node+1);
}
drvo[node] = drvo[2*node]+drvo[2*node+1];
}
ll get(int i,int j,int l,int r,int node){
if(j < l || i > r){
return 0;
}
if(l <= i && r >= j){
return drvo[node];
}
int mid = i+(j-i)/2;
return get(i,mid,l,r,2*node)+get(mid+1,j,l,r,2*node+1);
}
ll count_swaps(vector <int> S){
n = S.size();
for(int i = 1; i <= n; i++){
a[i] = S[i-1];
}
map <ll,ll> mapa;
for(int i = n; i >= 1; i--){
sled[i] = mapa[-a[i]];
mapa[a[i]] = i;
}
/*cout << endl;
for(int i = 1; i <= n; i++){
cout << sled[i] << " ";
}
cout << endl;*/
build(1,n,1);
ll sol = 0;
ll id = 1;
for(int t = 1; t <= n/2; t++){
ll poz = sled[id];
sol += get(1,n,id,poz,1)-2;
if(a[id] > 0){
sol++;
}
//cout << id << " " << poz << " " << sol << endl;
update(1,n,id,1);
update(1,n,poz,1);
if(sled[id] == id+1){
id += 2;
}
else{
id++;
}
}
return sol;
}
/*int main(){
vector <int> v = {-2, 2, 2, -2, -2, 2};
cout << count_swaps(v) << endl;
}*/
# | 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... |