Submission #211007

#	Time	Username	Problem	Language	Result	Execution time	Memory
211007		emanIaicepsa	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	107 ms	17324 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int bit[200005];
set<int> s1[100005];
set<int> s2[100005];
int n;
void add(int x,int val){
	for(int i=x;i<=n;i+=i&-i) bit[i]+=val;
}
ll query(int x){
	//cout<<x<<' ';
	ll ans = 0;
	for(int i=x;i;i-=i&-i) ans += bit[i];
	//cout<<ans<<'\n';
	return ans;
}

long long count_swaps(std::vector<int> arr) {
	n = arr.size();
	for(int i=1;i<=n;i++){
		add(i,1);
	}
	//cout<<"ok!\n";
	ll ans = 0;
	for(int i=1;i<=n;i++){
		int x = arr[i-1];
		if(x > 0){
			if(s2[x].empty()){
				s1[x].insert(i);
			}
			else{
				int p = *s2[x].begin() ; 
				s2[x].erase( s2[x].begin() );
				ans += query(i-1) - query(p);
				add(i,-1);
				add(p,1);
			}
		}
		else{
			x = -x;
			if(s1[x].empty()){
				s2[x].insert(i);
			}
			else{
				int p = *s1[x].begin();
				s1[x].erase( s1[x].begin() );
				ans += query(i-1) - query(p) + 1;
				add(i,-1);
				add(p,1);
			}
		}
	}
	//cout<<ans<<'\n';
	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