Submission #706232

#	Time	Username	Problem	Language	Result	Execution time	Memory
706232		Nonoze	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	132 ms	22448 KiB

shoes

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

struct segtree
{
	int size;
	vector<int> values;

	void init(int n) {
		size=1;
		while(size<n)size*=2;
		values.resize(2*size);
	}

	int calc(int i, int x, int qLeft, int qRight) {
		if (qLeft>i || qRight<i) return -1;
		if (qRight-qLeft == 1) return values[x];
		int mid=(qLeft+qRight) / 2;
		int s1=calc(i, 2*x, qLeft, mid);
		if (s1==-1) {
			s1 = calc(i, 2*x + 1, mid, qRight);
		}
		return values[x]+s1;
	}

	int calc(int i) {
		return calc(i, 1, 0, size);
	}

	void update(int x, int left, int right, int qLeft, int qRight) {
		if (qLeft>=right || qRight<=left) return;
		if (qLeft>=left && qRight<=right) {
			values[x]++;
			return;
		}
		int mid=(qLeft+qRight) / 2;
		update(x*2, left, right, qLeft, mid);
		update(x*2 + 1, left, right, mid, qRight);
	}
	void update(int left, int right) {
		update(1, left, right, 0, size);
	}

};

long long count_swaps(vector<int> s) {
	int n=s.size();
	vector<int> cnt[(int)2*n+5];
	vector<int> used(2*n+5, 0);
	vector<bool> visited(2*n+5, false);
	long long comp=0;
	segtree st;
	st.init(n);
	for (int i = 0; i < n; ++i)
	{
		cnt[s[i]+n].push_back(i);
	}
	for (int i = 0; i < n; ++i)
	{
		if (visited[i]) continue;
		int recherche=(-1*s[i])+n;
		int j=cnt[recherche][used[recherche]];
		comp-=(st.calc(i)-st.calc(j));
		//cout << i << ", " << j << ": " << st.calc(i) << " " << st.calc(j) << endl;
		st.update(i, j);
		if (s[i]<0) comp--;
		comp+=j-i;
		visited[j]=true;
		used[recherche]++;
		used[s[i]+n]++;
	}
	return comp;
}

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