Submission #797720

#	Time	Username	Problem	Language	Result	Execution time	Memory
797720		izanbf	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	356 ms	27688 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;

struct SegTree {
	vi st;
	int n;

	inline void merge(int p) {
		st[p] = st[2*p] + st[2*p+1];
	}

	void build(int p, int l, int r) {
		if (l == r) {
			st[p] = 1;
		}
		else {
			int m = (l+r)/2;
			build(2*p, l, m);
			build(2*p+1, m+1, r);
			merge(p);
		}
	}

	SegTree(int n_) {
		n = n_;
		st.resize(4*n);
		build(1, 0, n-1);
	}

	int count(int p, int l, int r, int i, int j) {
		if (r < i or l > j) return 0;
		if (i <= l and r <= j) return st[p];
		int m = (l+r)/2;
		return count(2*p, l, m, i, j) + count(2*p+1, m+1, r, i, j);
	}

	void upd(int p, int l, int r, int i, int x) {
		if (l == r) {
			st[p] = x;
		}
		else {
			int m = (l+r)/2;
			if (i <= m)
				upd(2*p, l, m, i, x);
			else
				upd(2*p+1, m+1, r, i, x);
			merge(p);
		}
	}

	void upd(int i, int x) { upd(1, 0, n-1, i, x); }
	int count(int i, int j) { return count(1, 0, n-1, i, j); }
};

ll count_swaps(vi s) {
	int n = s.size();

	map<int,vi> m;
	for (int i = 0; i < n; ++i) {
		m[s[i]].push_back(i);
	}
	for (auto& it : m) {
		reverse(it.second.begin(), it.second.end());
	}

	SegTree st(n);

	ll cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (st.count(i, i) == 1) {
			int j = m[-s[i]].back();

			cnt += st.count(i+1, j-1);
			if (s[i] > 0) ++cnt;

			st.upd(j, 0);
			m[s[i]].pop_back();
			m[s[j]].pop_back();
		}
	}

	return cnt;
}

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