Submission #152219

#	Time	Username	Problem	Language	Result	Execution time	Memory
152219		johutha	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	507 ms	282124 KiB

shoes

#include "shoes.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

#define int long long

using namespace std;

struct segtree
{
	vector<int> table;

	void update(int k, int v, int l, int r, int pos)
	{
		if (l == r)
		{
			table[pos] = v;
			return;
		}
		if (k <= (l + r) / 2) update(k, v, l, (l + r) / 2, 2*pos + 1);
		else update(k, v, (l + r)/ 2 + 1, r, 2*pos + 2);
		table[pos] = table[2*pos + 1] + table[2*pos + 2];
	}

	int query(int ql, int qr, int l, int r, int pos)
	{
		if (ql <= l && r <= qr) return table[pos];
		if (ql > r || qr < l) return 0;
		return query(ql, qr, l, (l + r)/2, 2*pos + 1) + query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2);
	}
};

long long count_swaps(vector<signed> s) {
	int n = s.size();

	vector<queue<int>> poss(n + 1);
	vector<queue<int>> negs(n + 1);

	for (int i = 0; i < n; i++)
	{
		if (s[i] < 0) negs[-s[i]].push(i);
		else poss[s[i]].push(i);
	}

	vector<int> seq(n, -1);
	int curr = 0;

	for (int i = 0; i < n; i++)
	{
		if (seq[i] != -1) continue;
		int v = abs(s[i]);
		if (s[i] < 0)
		{
			seq[i] = curr;
			seq[poss[v].front()] = curr + 1;
		}
		else
		{
			seq[negs[v].front()] = curr;
			seq[i] = curr + 1;
		}
		poss[v].pop();
		negs[v].pop();
		curr += 2;
	}
	/*
	for (auto i : seq) cout << i << " ";
	cout << "\n";
	*/
	int ssum = 0;
	segtree st;
	st.table.resize(4*n, 0);
	for (int i = 0; i < n; i++)
	{
		ssum += st.query(seq[i], n - 1, 0, n - 1, 0);
		st.update(seq[i], 1, 0, n - 1, 0);
	}
	return ssum;
}

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