Submission #813712

#	Time	Username	Problem	Language	Result	Execution time	Memory
813712		math_rabbit_1028	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	202 ms	141540 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll ans = 0;
vector<int> arr;

int tree[808080];

void init(int v, int st, int ed) {
	if (st == ed) {
		tree[v] = 1;
		return;
	}
	int mid = (st + ed) / 2;
	init(2 * v, st, mid);
	init(2 * v + 1, mid + 1, ed);
	tree[v] = tree[2 * v] + tree[2 * v + 1];
}

void update(int v, int st, int ed, int idx) {
	if (st > idx || ed < idx) return;
	if (st == idx && ed == idx) {
		tree[v] = 0;
		return;
	}
	int mid = (st + ed) / 2;
	update(2 * v, st, mid, idx);
	update(2 * v + 1, mid + 1, ed, idx);
	tree[v] = tree[2 * v] + tree[2 * v + 1];
}

int get(int v, int st, int ed, int lt, int rt) {
	if (st > rt || lt > ed) return 0;
	if (lt <= st && ed <= rt) return tree[v];
	int mid = (st + ed) / 2;
	return get(2 * v, st, mid, lt, rt) + get(2 * v + 1, mid + 1, ed, lt, rt);
}

deque<int> pdq[101010], mdq[101010];
long long count_swaps(std::vector<int> s) {
	arr = s;
	n = s.size()/2;

	for (int i = 0; i < 2 * n; i++) {
		if (s[i] > 0) pdq[s[i]].push_back(i);
		if (s[i] < 0) mdq[-s[i]].push_back(i);
	}

	init(1, 0, 2*n-1);

	for (int i = 0; i < 2 * n; i++) {
		if (get(1, 0, 2*n-1, i, i) == 0) continue;
		update(1, 0, 2*n-1, i);
		if (s[i] > 0) {
			pdq[s[i]].pop_front();
			int j = mdq[s[i]].front();
			mdq[s[i]].pop_front();
			ans += get(1, 0, 2*n-1, i + 1, j - 1) + 1;
			update(1, 0, 2*n-1, j);
		}
		if (s[i] < 0) {
			mdq[-s[i]].pop_front();
			int j = pdq[-s[i]].front();
			pdq[-s[i]].pop_front();
			ans += get(1, 0, 2*n-1, i + 1, j - 1);
			update(1, 0, 2*n-1, j);
		}
	}
	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