Submission #1226681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226681		repsak	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	328 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class SegmentTree{
	public:
		int length = 1;
		vector<ll> st;

		void setup(vector<int>& values){
			int N = values.size();
			while(length < N) length *= 2;

			st.resize(2 * length);
		}

		void update(int l, int r, int tl, int tr, int k){
			if(tl > r || tr < l) return;
			if(tl >= l && tr <= r){
				st[k] += 1;
				return;
			}

			int mid = (tl + tr) / 2;
			update(l, r, tl, mid, k * 2);
			update(l, r, mid + 1, tr, k * 2 + 1);
		}

		ll query(int index){	
			index += length;
			ll sum = st[index];

			for(int i = index / 2; i > 0; i /= 2){
				sum += st[i];
			}

			return sum;
		}
};


long long count_swaps(vector<int> s) {
	int N = s.size();

	map<int, set<int>> remain;
	map<int, int> counter;

	for(int i = 0; i < N; i++){
		remain[s[i]].insert(i);
	}

	SegmentTree tree;
	tree.setup(s);

	ll sum = 0;

	for(int i = 0; i < N; i++)
	{
		if(s[i] < 0 && counter[abs(s[i])] > 0 || s[i] > 0 && counter[abs(s[i])] < 0){
			int inc = s[i] > 0 ? 1 : -1;
			counter[abs(s[i])] += inc;
			continue;
		}
		int inc = s[i] > 0 ? 1 : -1;
		counter[abs(s[i])] += inc;

		int turn = *(remain[s[i]].begin());
		int other = *(remain[-1 * s[i]].begin());

		int additional = s[turn] > s[other] ? 1 : 0;
		int offset = abs(tree.query(turn) - tree.query(other));
		int diff = abs(turn - other) - 1;

		tree.update(turn, other, 0, tree.length - 1, 1);
		// Remove pair
		remain[s[i]].erase(remain[s[i]].begin());
		remain[-1 * s[i]].erase(remain[-1 * s[i]].begin());

		sum += additional + offset + diff;
	}

	return sum;
}

// #include "grader.cpp"

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