Submission #1248594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248594		M_W_13	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	147 ms	17704 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 20;
ll seg[2 * MAXN];

void upd(int l, int r) {
	l += MAXN;
	r += MAXN;
	while (l < r) {
		if (l % 2 == 1) {
			seg[l]++;
			l++;
		}
		if (r % 2 == 0) {
			seg[r]++;
			r--;
		}
		l /= 2;
		r /= 2;
	}
	if (l == r) {
		seg[l]++;
	}
}

ll query(int v) {
	ll ile = 0;
	v += MAXN;
	while (v > 0) {
		ile += seg[v];
		v /= 2;
	}
	return ile;
}

struct trojka {
	ll dl;
	int i, j;
};

bool por(trojka a, trojka b) {
	return a.dl < b.dl;
}

long long count_swaps(std::vector<int> s) {
	int n = ((int)s.size())/2;
	vector<ll> lewe[n + 1];
	vector<ll> prawe[n + 1];
	rep(i, 2 * n) {
		int x = abs(s[i]);
		if (s[i] < 0) {
			lewe[x].pb(i);
		}
		else {
			prawe[x].pb(i);
		}
	}
	ll ans = 0;
	vector<trojka> vec;
	rep(i, n + 1) {
		int sz = lewe[i].size();
		rep(j, sz) {
			if (lewe[i][j] < prawe[i][j]) {
				ans--;
			}
			ll dl = (lewe[i][j] + prawe[i][j]);
			vec.pb({dl, i, j});
		}
	}
	sort(vec.begin(), vec.end(), por);
	rep(i, n) {
		int x = vec[i].i;
		int y = vec[i].j;
		ll a = lewe[x][y] + query(lewe[x][y]);
		ll b = prawe[x][y] + query(prawe[x][y]);
		upd(0, lewe[x][y]);
		upd(0, prawe[x][y]);
		ll k = 2 * i;
		// cout << "a = " << a << " b = " << b << " k = " << k << '\n';
		ans += (a + b - 2 * k);
	}
	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