Submission #545479

#	Time	Username	Problem	Language	Result	Execution time	Memory
545479		LunaMeme	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	348 ms	149916 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
const int MAXN  = 2e5 + 5;
ll tree[MAXN];
void update(int a, int u){
	a ++;
	for(int k = a; k < MAXN; k += (k & -k)){
		tree[k] += u;
	}
}
ll sum(int a){
	a ++;
	ll res = 0;
	for(int k = a; k >= 1; k -=(k &-k)){
		res += tree[k];
	}
	//cout << a << "  sum = " << res << '\n';
	return res;
}
long long count_swaps(std::vector<int> s) {
	memset(tree, 0, sizeof tree);
	unordered_map<int, deque<int>> pos;
	int sz = s.size();
	for(int i = sz - 1; i >= 0; i--){
		pos[s[i]].PB(i);
	}
	vector<bool> removed(sz, false);
	ll swaps = 0;
	vi d(2*sz, 0);//difference array for num of removed to right of it

	for(int i = sz - 1; i >= 0; i --){
		if (removed[i]) continue;
		int pair = pos[-s[i]].front();
		//cout << i << "  pair index : " << pair << '\n';
		pos[-s[i]].pop_front();
		pos[s[i]].pop_front();
		swaps += (i - pair - 1);
		swaps -= sum(pair) - sum(i); 
		//update d in range 0 to pair
		update(0, 1);
		update(pair, -1);
		if (s[i] < 0){
			swaps ++;
		}
		removed[pair] = true;
		//cout << swaps << '\n';
	}
	return swaps;
}

/*
int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
*/

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