Submission #873673

#	Time	Username	Problem	Language	Result	Execution time	Memory
873673		Cutebol	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	406 ms	31628 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_pbds;
tree < int , null_type , less < int > , rb_tree_tag,tree_order_statistics_node_update > st ;
const int N = 2e6 + 5 ;
#define ll long long
map <ll , set <ll>> l , r ;
bool f[N] ;

long long count_swaps(vector<int> s) {
	ll n = s.size() , ans = 0 ;
	for ( int i = 0 ; i < n ; i ++ ){
		if ( s[i] < 0 ) l[-s[i]].insert(i) ;
		else r[s[i]].insert(i) ;
	}
	for ( int i = 0 ; i < n ; i ++ ){
		if ( f[i] == 1 ){ st.erase(i); continue ;}
		if ( s[i] < 0 ){
			int ind = *r[-s[i]].begin() ;
			r[-s[i]].erase(r[-s[i]].begin()) ;
			l[-s[i]].erase(l[-s[i]].begin()) ;
			int x = st.order_of_key(ind) ;
			st.insert(ind) ;
			ans += ind-i-1-x ;
			f[ind] = 1 ;
		}
		else{
			int ind = *l[s[i]].begin() ;
			l[s[i]].erase(l[s[i]].begin()) ;
			r[s[i]].erase(r[s[i]].begin()) ;
			int x = st.order_of_key(ind) ;
			st.insert(ind) ;
			ans += ind-i-x ;
			f[ind] = 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