Submission #863405

#	Time	Username	Problem	Language	Result	Execution time	Memory
863405		20163070	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	49 ms	21504 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

const int N=4e5+10;

int n;
int tr[N];
int vis[N];
int a[N];
vector<int> pos[N];

int lowbit(int x)
{
	return x&-x;
}

int sum(int x)
{
	int res=0;
	for(int i=x;i;i-=lowbit(i)) res+=tr[i];
	return res;
}

void add(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tr[i]+=c;
}

long long count_swaps(std::vector<int> s) {
	n=s.size();
	for(int i=0;i<n;i++) a[i+1]=s[i];
	for(int i=1;i<=n;i++)
	{
		pos[a[i]+n].push_back(i);
		add(i,1);
	}
	long long ans=0;
	for(int i=n;i>=1;i--)
	{
		if(vis[i]) continue;
		vis[i]=1;
		pos[a[i]+n].pop_back();
		int res=pos[n-a[i]].back();
		pos[n-a[i]].pop_back();
		vis[res]=1;
		ans=ans+(long long)(sum(i-1)-sum(res))+((a[i]<0)?1:0);
		add(res,-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