Submission #618713

#	Time	Username	Problem	Language	Result	Execution time	Memory
618713		pirhosig	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	691 ms	155012 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define ll long long
using namespace std;



struct segTree
{
	vector<int> nodes;
	vector<int> lazy;

	segTree(int s) : nodes(s * 4) {}

	void update(int n, int tl, int tr, int l, int r, int val) {
		if (l <= tl && tr <= r) {
			nodes[n] += val;
			return;
		}
		int tm = (tl + tr) / 2;
		if (l <= tm) update(n * 2, tl, tm, l, r, val);
		if (tm + 1 <= r) update(n * 2 + 1, tm + 1, tr, l, r, val);
	}

	int query(int n, int tl, int tr, int pos) {
		int res = nodes[n];
		if (tl == tr) return res;
		int tm = (tl + tr) / 2;
		if (pos <= tm) res += query(n * 2, tl, tm, pos);
		else res += query(n * 2 + 1, tm + 1, tr, pos);
		return res;
	}
};



ll count_swaps(vector<int> s) {
	int DN = s.size();
	segTree tree(DN);

	for (int i = 1; i <= DN; ++i) {
		tree.update(1, 1, DN, i, i, i);
	}

	ll tot = 0;

	set<ii> ops;
	map<int, queue<int>> pq;
	for (int i = 0; i < DN; ++i) {
		int a = s[i];
		if (pq[-a].size()) {
			int b = pq[-a].front();
			pq[-a].pop();
			ops.insert({b, i});
			if (a < 0) tot++;

			// cerr << "P " << b << " " << i << endl;
		}
		else pq[a].push(i);
	}

	for (auto a : ops) {
		int p1 = tree.query(1, 1, DN, a.first + 1);
		int p2 = tree.query(1, 1, DN, a.second + 1);
		tot += p2 - p1 - 1;
		tree.update(1, 1, DN, a.first + 1, DN, -1);
		tree.update(1, 1, DN, a.second + 1, DN, -1);
	}

	return tot;
}

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