| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 802363 | Benmath | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int tree[800001];
void update(int node,int start,int end,int idx,int val){
if(start==end){
tree[node]+=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
update(2*node,start,mid,idx,val);
}else{
update(2*node+1,mid+1,end,idx,val);
}
tree[node]=tree[2*node]+tree[2*node+1];
}
}
int query(int node,int start,int end,int l,int r){
if(l<=start and end<=r){
return tree[node];
}
if(r<start or end<l){
return 0;
}
int mid=(start+end)/2;
return query(2*node,start,mid,l,r)+query(2*node+1,mid+1,end,l,r);
}
long long count_swaps(std::vector<int> s) {
int n=s.size();
n=n/2;
int ropos[n+1];
int roneg[n+1];
vector<int>vpos[n+1];
vector<int>vneg[n+1];
for(int i=0;i<=n;i++){
ropos[i]=0;
roneg[i]=0;
}
for(int i=0;i<2*n;i++){
if(s[i]>0){
vpos[s[i]].push_back(i);
}else{
vneg[abs(s[i])].push_back(i);
}
}
long long int sum=0;
for(int i=0;i<2*n;i=i+2){
int x1=i;
int x2=i+1;
int l=0;
int r=i;
while(l<=r){
int mid=(l+r)/2;
int ro=query(1,0,2*n-1,mid,2*n-1)+mid;
if(ro>=i){
x1=min(x1,mid);
r=mid-1;
}else{
l=mid+1;
}
}
l=0;
r=i+1;
while(l<=r){
int mid=(l+r)/2;
int ro=query(1,0,2*n-1,mid,2*n-1)+mid;
if(ro>=(i+1)){
x2=min(x2,mid);
r=mid-1;
}else{
l=mid+1;
}
}
int tren1=s[x1];
int tren2=s[x2];
if((tren1+tren2)!=0){
int ind;
if(tren1>0){
ind=vneg[tren1][roneg[tren1]];
}else{
ind=vpos[abs(tren1)][ropos[abs(tren1)]];
} int ind1=ind;
if(ind1!=(2*n-1)){
ind=ind1+query(1,0,2*n-1,ind1+1,2*n-1);
}
sum=sum+(ind-(i+1));
update(1,0,2*n-1,ind1,1);
// cout<<sum<<" "<<tren1<<" "<<ind<<" "<<ind1<<" "<<query(1,0,2*n-1,0,2*n-1)<<" "<<endl;
}
ropos[abs(tren1)]++;
roneg[abs(tren1)]++;
if(tren1>0){
sum++;
}
}
return sum;
}
int main() {
int n;
assert(1 == scanf("%d", &n));
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
assert(1 == scanf("%d", &S[i]));
fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
fclose(stdout);
return 0;
}