Submission #605520

#	Time	Username	Problem	Language	Result	Execution time	Memory
605520		misteg168	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	684 ms	151272 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second

ll get(ll x){
	ll y = 0;
	while((1ll<<y) < x) y++;
	return (1ll << y);
}

void upd(vector<ll> & segtree, ll a, ll t){
	a += t;
	while(a > 0){
		segtree[a]++;
		a/=2;
	}
}

ll rg(vector<ll> & segtree, ll a, ll b, ll t){
	a += t, b += t;
	ll ans = 0;
	while(a <= b){
		if(a % 2 == 1) ans += segtree[a++];
		if(b % 2 == 0) ans += segtree[b--];
		a /= 2, b/= 2;
	}
	return ans;
}

long long count_swaps(std::vector<int> s) {
	ll n = s.size();
	map<ll, deque<ll>> v;
	for(int i = 0; i < n; i++){
		v[-s[i]].push_back(i);
	}
	ll t = get(n);
	vector<ll> segtree(2*t);
	vector<bool> pos(n, 0);
	ll ans = 0;
	for(int i = 0; i < n; i++){
		if(pos[i]){
			continue;
		}
		ans += v[s[i]][0]-i-rg(segtree, i, v[s[i]][0], t);
		if(s[i] < 0) ans--; //not need to swap shoes
		pos[i] = 1;
		upd(segtree, v[s[i]][0], t);
		pos[ v[s[i]][0] ] = 1;
		v[ -s[i] ].pop_front();
		v[ s[i] ].pop_front();
	}
	
	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