Submission #1248902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248902		lfe	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	101 ms	6680 KiB

shoes

#include "shoes.h"
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

int sum(int a, int b, int m, vector<int>& tree) {
	int ut = 0;
	a += m; b += m;
	while (a <= b) {
		if (a%2 == 1) ut += tree[a++];
		if (b%2 == 0) ut += tree[b--];
		a /= 2; b /= 2;
	}
	return ut;
}

void add(int x, int k, int m, vector<int>& tree) {
	k += m;
	tree[k] += x;
	for (k /= 2; k >= 1; k /= 2) {
		tree[k] = tree[2*k] + tree[2*k+1];
	}
}


long long count_swaps(std::vector<int> s) {
	int tot = 0;

	int n = s.size();
	vector<pair<int,int>> par;
	map<int, int> sett;

	for (int i = 0; i < n; i++) {
		if (sett.count(-s[i])) {
			par.emplace_back(sett[-s[i]], i);
			sett.erase(-s[i]);
		}
        else {
			if (s[i] > 0) ++tot;
			sett[s[i]] = i;
		}
	}

	sort(par.begin(), par.end());

	int x = ceil(log2(n));
    int m = 1 << x;
	vector<int> tree(2*m, 0);
	for (int i = 0; i < n; i++) add(1, i, m, tree);

	for (pair<int, int> p: par) {
		tot += sum(p.first + 1, p.second - 1, m, tree);
		add(-1, p.first, m, tree); add (-1, p.second, m, tree);
	}

	return tot;
}

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