Submission #442590

#	Time	Username	Problem	Language	Result	Execution time	Memory
442590		zxcvbnm	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	164 ms	22716 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
4
1 2 3 -4 4 -2 -1 -3

4
1 2 3 -4 -2 4 -1 -3

5
3 2 2 -2 3 2 -3 -2 -2 -3

4
1 2 3 4 -4 -3 -2 -1

5
1 2 3 4 4 -1 -2 -3 -4 -4

5

*/
struct SegTree {
	int n;
	vector<int> tree;
	void build(int sz) {
		n = 1;
		while(n < sz) {
			n *= 2;
		}
		tree.assign(2*n, 0);
	}
	void set(int id, int val) {
		set_r(0, 0, n, id, val);
	}
	void set_r(int idx, int l, int r, int& id, int& val) {
		if (r - l == 1) {
			tree[idx] = val;
			return;
		}

		int mid = (l + r) / 2;
		if (id < mid) {
			set_r(2*idx+1, l, mid, id, val);
		} else {
			set_r(2*idx+2, mid, r, id, val);
		}

		tree[idx] = tree[2*idx+1] + tree[2*idx+2];
	}

	int sum(int L, int R) {
		return sum_r(0, 0, n, L, R);
	}
	int sum_r(int idx, int l, int r, int& L, int& R) {
		if (l >= R || r <= L) return 0;
		if (l >= L && R >= r) return tree[idx];

		int mid = (l + r) / 2;
		int s1 = sum_r(2*idx+1, l, mid, L, R);
		int s2 = sum_r(2*idx+2, mid, r, L, R);
		return s1 + s2;
	}
};

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

	ll sum = 0;
	SegTree st;
	st.build(n);
	map<int, int> cnt;
	vector<int> idx[n+1][2];
	for(int i = 0; i < n; i++) {
		idx[abs(a[i])][a[i]>0].push_back(i);
	}

	vector<pair<int, int>> id;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j < (int) idx[i][0].size(); j++) {
			if (idx[i][0][j] < idx[i][1][j]) {
				swap(idx[i][0][j], idx[i][1][j]);
			} else {
				sum++;
			}
			id.push_back({idx[i][0][j], idx[i][1][j]});
		}
	}

	sort(id.begin(), id.end());
	for(auto i : id) {
		sum += (i.first-i.second-1);
		sum -= st.sum(i.second, i.first);
		st.set(i.first, 1);
		st.set(i.second, -1);
	}
	return sum;
}

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