Submission #442649

#	Time	Username	Problem	Language	Result	Execution time	Memory
442649		BT21tata	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	133 ms	17848 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
using namespace std;

vector<pii>w;
vector<int> a[100005], b[100005];
ll t[800005];

void push(int v)
{
	t[v<<1]+=t[v];
	t[v<<1|1]+=t[v];
	t[v]=0;
}

int get(int v, int l, int r, int x)
{
	if(l==r) return t[v];
	push(v);
	int m=(l+r)>>1;
	if(x<=m) return get(v<<1, l, m, x);
	else return get(v<<1|1, m+1, r, x);
}

void add(int v, int l, int r, int tl, int tr)
{
	if(l!=r) push(v);
	if(tr<=l or r<=tl) return;
	else if(tl<=l and r<=tr)
	{
		t[v]+=1;
	    return;
	}
	int m=(l+r)>>1;
	add(v<<1, l, m, tl, tr);
	add(v<<1|1, m+1, r, tl, tr);
}

long long count_swaps(vector<int>s)
{
	int n=(int)s.size() >> 1;
	ll ans=0;
	for(int i=0; i<2*n; i++)
	{
		if(s[i]<0) a[-s[i]].pb(i);
		else b[s[i]].pb(i);
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<(int)a[i].size(); j++)
		{
			if(a[i][j]>b[i][j])
			{
				ans++;
				w.pb({b[i][j], a[i][j]});
			}
			else w.pb({a[i][j], b[i][j]});
		}
	}
	sort(w.begin(), w.end());
	for(pii u : w)
	{
		ll x=u.F+get(1, 0, 2*n-1, u.F);
		ll y=u.S+get(1, 0, 2*n-1, u.S);
		ans+=(y-x-1);
		add(1, 0, 2*n-1, u.F, u.S);
	}
	return ans;
}
/*
3
-2 2 2 -2 -2 2
*/

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