Submission #1174948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174948		Clan328	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	0 ms	328 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;

	// int n = s.size()/2;
	// if (n == 0) return 0;

	// // Compress
	// set<int> visited;
	// for (int i = 0; i < 2*n; i++) {
	// 	visited.insert(abs(s[i]));
	// }
	// map<int, int> mapper;
	// int idx = 1;
	// for (auto x : visited) {
	// 	mapper[x] = idx++;
	// }

	// for (int i = 0; i < 2*n; i++) {
	// 	if (s[i] > 0) s[i] = mapper[s[i]];
	// 	else s[i] = -mapper[-s[i]];
	// }

	// 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);
	// }

	// int curr = -1, calc = 1e7;
	// for (int i = 1; i <= n; i++) {
	// 	if (left[i].size() == 0) continue;
	// 	int tmp = left[i][0]+right[i][0]-((left[i][0] < right[i][0])? 1 : 0);
	// 	if (tmp < calc) {
	// 		curr = i;
	// 		calc = tmp;
	// 	}
	// }

	// assert(curr != -1);

	// vector<int> newS;
	// for (int i = 0; i < 2*n; i++) {
	// 	if (i == left[curr][0]) continue;
	// 	if (i == right[curr][0]) continue;

	// 	newS.push_back(s[i]);
	// }

	// return calc + count_swaps(newS);
}

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