Submission #826851

#	Time	Username	Problem	Language	Result	Execution time	Memory
826851		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	272 ms	25420 KiB

shoes

#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

using namespace std;

const int maxn=2e5+10;

int n, fen[maxn];

void upd(int r, int val)
{
	for(; r <= n; r = ((r + 1) | r))
	{
		fen[r] += val;
	}
}

int get(int r)
{
	int s = 0;
	for(; r >= 0; r = ((r + 1) & r) - 1)
	{
		s += fen[r];
	}
	return s;
}

long long count_swaps(std::vector<int> S)
{
	n = S.size();
	map <int, vector <int> > mapp;
	vector <int> del(n, 0);
	for(int i = n-1; i >= 0; --i)
	{
		mapp[S[i]].pb(i);
		upd(i, 1);
	}
	ll ans = 0;
	FOR(0, i, n)
	{
		if(del[i]) continue;
		int pos = mapp[-S[i]].back();
		mapp[-S[i]].pop_back();
		mapp[S[i]].pop_back();
		ans += get(pos)-get(i) - (S[i] < 0);
		del[pos] = 1;
		upd(pos, -1);
	}
	return ans;
}

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