Submission #568455

#	Time	Username	Problem	Language	Result	Execution time	Memory
568455		d4xn	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	558 ms	41052 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define vi vector<ll>

const ll N = 1 << 20;

ll n;
ll lazy[N];
ll seg[N];

void build(ll p = 1, ll l = 0, ll r = n-1) {
	if (l > r) return;

	if (l == r) {
		seg[p] = l;
		return;
	}

	ll mid = (l+r)/2;
	build(p*2, l, mid);
	build(p*2+1, mid+1, r);

	seg[p] = min(seg[p*2], seg[p*2+1]);
}

void pushDown(ll p) {
	for (ll h : {p*2, p*2+1}) {
		lazy[h] += lazy[p];
		seg[h] += lazy[p];
	}
	lazy[p] = 0;
}

void update(ll a, ll p = 1, ll l = 0, ll r = n-1) {
	if (l > r || r < a) return;

	if (a <= l) {
		lazy[p]--;
		seg[p]--;
		return;
	}

	if (lazy[p] != 0) pushDown(p);

	ll mid = (l+r)/2;
	update(a, p*2, l, mid);
	update(a, p*2+1, mid+1, r);

	seg[p] = min(seg[p*2], seg[p*2+1]);
}

ll query(ll idx, ll p = 1, ll l = 0, ll r = n-1) {
	if (l > r || idx < l || idx > r) return 0;

	if (l == r) {
		if (l == idx) return seg[p];
		return 0;
	}

	if (lazy[p] != 0) pushDown(p);

	ll mid = (l+r)/2;
	ll a = query(idx, p*2, l, mid);
	ll b = query(idx, p*2+1, mid+1, r);

	return a+b;
}

long long count_swaps(std::vector<int> s) {
	ll swaps = 0;
	n = s.size();

	build();

	map<ll, ll> last; // ultima aparicion de zapatilla con sz x
	vi next(n, -1); // idx de la pareja mas cercana de la zapatilla i
	vi nextSame(n, -1); // idx de la zapatilla mas cercana de la misma sz
	for (ll i = n-1; i >= 0; i--) {
		if (last.count(-s[i])) next[i] = last[-s[i]];
		if (last.count(s[i])) nextSame[i] = last[s[i]];
		last[s[i]] = i;
	}

	vi vis(n, 0);
	map<ll, ll> newNext; // nueva pareja mas cercana para zapatilla de sz x
	map<ll, ll> newNextSame; // nueva zapatilla igual mas cercana para zapatilla de sz x
	for (ll i = 0; i < n; i++) {
		if (vis[i]) continue;

		if (newNext.count(s[i])) {
			if (newNext[s[i]] < next[i]) {
				newNext.erase(s[i]);
			}
			else {
				next[i] = newNext[s[i]];
			}
		}

		if (newNextSame.count(s[i])) {
			if (newNextSame[s[i]] < nextSame[i]) {
				newNextSame.erase(s[i]);
			}
			else {
				nextSame[i] = newNextSame[s[i]];
			}
		}
		
		// buscar zapatilla derecha de sz abs(s[i]) mas cercana
		// y ponerla a la derecha
		ll idx = next[i];
		swaps += query(idx) - query(i) - 1;

		if (newNextSame.count(-s[i])) {
			if (newNextSame[-s[i]] > nextSame[idx]) {
				nextSame[idx] = newNextSame[-s[i]];
			}
		}

		ll nx = nextSame[idx];
	
		if (newNext.count(s[i])) newNext[s[i]] = max(newNext[s[i]], nx);
		else newNext[s[i]] = nx;

		if (newNextSame.count(-s[i])) newNextSame[-s[i]] = max(newNextSame[-s[i]], nx);
		else newNextSame[-s[i]] = nx;

		vis[idx] = 1;
		update(idx+1);

		if (s[i] > 0) swaps++;
	}

	return swaps;
}

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