Submission #202548

#	Time	Username	Problem	Language	Result	Execution time	Memory
202548		batmend_kh	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	253 ms	141056 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;

queue <int> pos[2 * N];
bool staying[2 * N];
long long ans;
int tree[8 * N];

void build_tree(int l, int r, int k);
void change_val(int l, int r, int pos, int k);
int find_sum(int l, int r, int ll, int rr, int k);

long long count_swaps(std::vector<int> s) {
	memset(staying, 1, sizeof staying);
	int n2 = s.size();
	build_tree(0, n2 - 1, 1);

	for (int i = 0; i < n2; i++) {
		int val = N + s[i];
		pos[val].push(i);
	}

	for (int i = 0; i < n2; i++) {

		if (staying[i] == 0) continue;
		pos[N + s[i]].pop();
		int srchval = N - s[i];
		int ind = pos[srchval].front();
		pos[srchval].pop();
		ans += find_sum(0, n2 - 1, i + 1, ind - 1, 1);
		if (s[i] > 0) ans++;
		staying[ind] = 0;
		change_val(0, n2 - 1, ind, 1);
	}
	return ans;
}	







void change_val(int l, int r, int pos, int k) {
	if (l == pos && r == pos) {
		tree[k] = 0;
		return;
	}
	if (pos < l || r < pos) return;
	int mid = (l + r) / 2;
	change_val(l, mid, pos, 2*k);
	change_val(mid + 1, r, pos, 2*k+1);
	tree[k] = tree[2*k] + tree[2*k+1];
}


void build_tree(int l, int r, int k) {
	if (l == r) {
		tree[k] = staying[l]; 
		return;
	}
	int mid = (l + r) / 2;
	build_tree(l, mid, 2 * k);
	build_tree(mid + 1, r, 2 * k + 1);
	tree[k] = tree[2*k] + tree[2*k + 1];
}

int find_sum(int l, int r, int ll, int rr, int k) {
	if (rr < ll) return 0;
	if (r < ll || rr < l) return 0;
	if (ll <= l && r <= rr) return tree[k];
	int mid = (l + r) / 2;
	int ff = find_sum(l, mid, ll, rr, 2*k);
	int ss = find_sum(mid + 1, r, ll, rr, 2*k + 1);
	return ff + ss;
}

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