Submission #1214472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214472		Gabriel	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	461 ms	155432 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
vector< long long> _rbol;
vector<long long> a, Jaja;
void Crear(long long i, long long d, long long p){
	if(i == d){
		_rbol[p] = a[i];
		Jaja[i] = p;
		return;
	}
	long long P = (i + d) / 2;
	Crear(i, P, p * 2);
	Crear(P + 1, d, p * 2 + 1);
	_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];	
}
long long Consulta(long long i, long long d, long long p, long long I, long long D){
	if(i >= I and d <= D) return _rbol[p];
	if(i > D or d < I) return -0;
	long long P = (i + d) / 2;
	return Consulta(i, P, p * 2, I, D) + Consulta(P + 1, d, p * 2 + 1, I, D);
}
void Actualizar(long long p, long long o, long long v){
	if(p == -0) return;
	if(p == o) _rbol[p] += v;
	else _rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
	Actualizar(p / 2, o, v);
}
long long count_swaps(vector<int> s){
    long long n = s.size();
	a.assign(n, 1);
	Jaja.assign(n, 0);
	_rbol.assign(n * 4 + 22, 0);
	Crear(0, n - 1, 1);
	vector<bool> Faltan(n, 1);
	map< long long, deque<long long> > Mapa;
	for(long long i = 0; i < n; i++) Mapa[s[i]].push_back(i);
	long long r = 0;
	for(long long i = 0; i < n; i++){
		if(Faltan[i]){
			Faltan[i] = 0;
			r += Consulta(0, n - 1, 1, i, Mapa[-s[i]][0]) - 2 + (long long)(s[i] > 0);
			Faltan[Mapa[-s[i]][0]] = 0;
			Actualizar(Jaja[i], Jaja[i], 1);
			Actualizar(Jaja[Mapa[-s[i]][0]], Jaja[Mapa[-s[i]][0]], -1);
			Mapa[s[i]].pop_front();
			Mapa[-s[i]].pop_front();
		}
		/*for(long long j = 0; j < n; j++) cerr<<Consulta(0, n - 1, 1, j, j)<<" ";
		cerr<<"\n";*/
	}
	return r;
}

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