Submission #1097857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097857		Newtonabc	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	198 ms	274824 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int MIDX=2e5;
int n,fw[N],arr[N];
stack<int> pos[N],rpos[N];
void update(int idx,int val){
	while(idx<=MIDX){
		fw[idx]+=val;
		idx+=idx & -idx;
	}
}
long long read(int idx){
	long long sum=0;
	while(idx>0){
		sum+=fw[idx];
		idx-=idx & -idx;
	}
	return sum;
}
long long count_swaps(vector<int> s) {
	n=s.size()/2;
	int lidx,ridx;
	long long ans=0;
	for(int i=1;i<=2*n;i++) arr[i]=s[i-1],update(i,1);
	for(int i=2*n;i>=1;i--){
		if(arr[i]<0) rpos[-arr[i]].push(i);
		else pos[arr[i]].push(i);
	}
	for(int i=1;i<=2*n;i++){
		//cout<<pos[2].top() <<" " <<rpos[2].top() <<"\n";
		if(read(i)-read(i-1)==0) continue;
		if(arr[i]<0){
			lidx=i;
			ridx=pos[-arr[i]].top();
			pos[-arr[i]].pop(),rpos[-arr[i]].pop();
			ans+=read(ridx)-read(lidx)-1;
			//cout<<read(ridx) <<" " <<read(lidx) <<"\n";
			update(lidx,-1),update(ridx,-1);
			continue;
		}
		ridx=i;
		lidx=rpos[arr[i]].top();
		rpos[arr[i]].pop(),pos[arr[i]].pop();
		ans+=read(lidx)-read(ridx);
		//cout<<read(lidx) <<" " <<read(ridx) <<"\n";
		update(lidx,-1),update(ridx,-1);
	}
	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15