Submission #1174953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174953		Clan328	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	74 ms	16812 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
	vector<int> t;

	SegmentTree(int n) {
		t = vector<int>(4*n);
	}

	void update(int v, int tl, int tr, int pos, int x) {
		if (tl == tr) {
			t[v] = x;
		} else {
			int tm = (tl+tr)/2;

			if (pos <= tm)
				update(2*v, tl, tm, pos, x);
			else
				update(2*v+1, tm+1, tr, pos, x);

			t[v] = (t[2*v] + t[2*v+1]);
		}
	}

	int get(int v, int tl, int tr, int l, int r) {
		if (l > r) return 0;
		else if (tl == l && r == tr) return t[v];
		else {
			int tm = (tl+tr)/2;

			return (get(2*v, tl, tm, l, min(tm, r)) + get(2*v+1, tm+1, tr, max(l, tm+1), r));
		}
	}
};

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;

	long long res = 0;
	vector<vector<int>> left(n+1), right(n+1);
	for (int i = 0; i < 2*n; i++) {
		if (s[i] < 0) left[abs(s[i])].push_back(i);
		else right[abs(s[i])].push_back(i);
	}
	vector<int> nxt(2*n, -1);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < left[i].size(); j++) {
			if (left[i][j] > right[i][j]) {
				s[left[i][j]] *= -1;
				s[right[i][j]] *= -1;
				res++;
				nxt[right[i][j]] = left[i][j];
			} else {
				nxt[left[i][j]] = right[i][j];
			}
		}
	}

	SegmentTree tree(2*n);
	for (int i = 0; i < 2*n; i++) {
		tree.update(1, 0, 2*n-1, i, s[i]/abs(s[i]));
	}

	for (int i = 0; i < 2*n; i++) {
		if (s[i] > 0) continue;
		res += nxt[i]-i-1;
		tree.update(1, 0, 2*n-1, i, 0);
		tree.update(1, 0, 2*n-1, nxt[i], 0);
		res -= tree.get(1, 0, 2*n-1, nxt[i]+1, 2*n-1);
	}

	return res;
}

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