Submission #596117

#	Time	Username	Problem	Language	Result	Execution time	Memory
596117		AriaH	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	400 ms	24584 KiB

shoes

#include "shoes.h"
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;

int Mat[N], fen[N];

void add(int i, int x)
{
	for(i += 3; i < N; i += i & -i)
	{
		fen[i] += x;
	}
}

int ask(int i, int ret = 0)
{
	for(i += 3; i; i -= i & -i)
	{
		ret += fen[i];
	}
	return ret;
}

ll count_swaps(vector < int > s)
{
	int n = SZ(s);
	map < int, vector < int > > mp;
	for(int i = n - 1; ~i; i --)
	{
		mp[s[i]].push_back(i);
	}
	ll tot = 0;
	for(int i = 0; i < n; i ++)
	{
		if(SZ(mp[s[i]]) && mp[s[i]].back() == i)
		{
			mp[s[i]].pop_back();
			int nxt = mp[-s[i]].back();
			mp[-s[i]].pop_back();
			int dis = abs(nxt - i - 1) - (ask(nxt) - ask(i));
			tot += dis;
			if(s[i] > 0) tot ++;
			add(nxt, 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