Submission #399549

#	Time	Username	Problem	Language	Result	Execution time	Memory
399549		abra_stone	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	187 ms	142404 KiB

shoes

#include "shoes.h"
#include <queue>
#define N 100000
using namespace std;

typedef long long ll;
ll n, ba, ans, sg[N * 8 + 5];
bool v[N * 2];
queue<int> qu[N * 2 + 5];

ll ge(ll p, ll q) {
	ll re = 0;
	p += ba; q += ba;
	while (p < q) {
		if (p % 2 == 1) re += sg[p], p++;
		if (q % 2 == 0) re += sg[q], q--;
		p /= 2; q /= 2;
	}
	if (p == q) re += sg[p];
	return re;
}

void up(ll p) {
	p += ba;
	sg[p] = 0;
	for (p /= 2; p > 0; p /= 2) sg[p] = sg[p * 2] + sg[p * 2 + 1];
}

ll count_swaps(vector<int> s) {
	ll i, fu;
	n = s.size();
	for (i = 0; i < n; i++) qu[s[i] + N].push(i);
	for (ba = 1; ba < n; ba *= 2);
	for (i = 0; i < n; i++) sg[i + ba] = 1;
	for (i = ba - 1; i > 0; i--) sg[i] = sg[i * 2] + sg[i * 2 + 1];
    for (i = 0; i < n; i++) {
		if (v[i]) continue;
		ll t = s[i] * -1 + N;
		while (!qu[t].empty()) {
			fu = qu[t].front(), qu[t].pop();
			if (!v[fu]) break;
		}
		v[i] = v[fu] = 1;
		ans += ge(i, fu - 1);
		if (s[i] < 0) ans--;
		up(fu);
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:44:12: warning: 'fu' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |   ans += ge(i, fu - 1);
      |          ~~^~~~~~~~~~~

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