Submission #151751

#	Time	Username	Problem	Language	Result	Execution time	Memory
151751		mieszko11b	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	107 ms	15196 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct fenwickTree {
	int n;
	vector<int> d;
	
	void add(int i, int x) {
		i++;
		for( ; i <= n ; i += (i & (-i)))
			d[i] += x;
	}
	
	int sum(int a) {
		a++;
		int res = 0;
		for( ; a > 0 ; a -= (a & (-a)))
			res += d[a];
		return res;
	}
	
	fenwickTree(int _n) {
		n = _n;
		d.resize(n + 3, 0);
		for(int i = 0 ; i < n ; i++)
			add(i, 1);
	}
};

int n;
fenwickTree FT(200007);
vector<int> pos[200007];
bool del[200007];

long long count_swaps(std::vector<int> s) {
	ll res = 0;
	
	n = s.size() / 2;
	for(int i = 0 ; i < 2 * n ; i++)
		pos[s[i] + n].push_back(i);
	for(int i = 0 ; i< 200007 ; i++)
		reverse(pos[i].begin(), pos[i].end());
		
	for(int i = 0 ; i < 2 * n ; i++) {
		if(del[i])
			continue;
			
		if(s[i] > 0)
			res++;
			
		FT.add(i, -1);
		int other = pos[-s[i] + n].back();
		pos[-s[i] + n].pop_back();
		del[other] = del[i] = 1;
		pos[s[i] + n].pop_back();
		
		FT.add(other, -1);
		res += FT.sum(other);
	}
	
	return res;
}

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