Submission #152804

#	Time	Username	Problem	Language	Result	Execution time	Memory
152804		tinjyu	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	130 ms	12920 KiB

shoes

#include "shoes.h"
#include <iostream>
using namespace std;
long long int tag[1000005],l,r,n,tree[1000005],map[1000005],road[1000005];
long long int change(int s,int e,int t)
{
	if(l<s || l>e)return tree[t];
	if(s==e)return tree[t]=1;
	return tree[t]=change(s,(s+e)/2,t*2)+change((s+e)/2+1,e,t*2+1);
}
long long int find(int s,int e,int t)
{
	if(l>e || r<s)return 0;
	if(l<=s && e<=r)return tree[t];
	return find(s,(s+e)/2,t*2)+find((s+e)/2+1,e,t*2+1);
}
long long count_swaps(std::vector<int> s) {
	n=s.size();
	n/=2;
	for(int i=0;i<=200000;i++)road[i]=-1;
	for(int i=2*n-1;i>=0;i--)
	{
		if(s[i]<0)
		{
			s[i]*=-1;
			s[i]+=200000;
		}
		map[i]=road[s[i]];
		road[s[i]]=i;
	}
	long long int ans=0;
	for(int i=0;i<2*n-1;i++)
	{
		if(tag[i]==1)continue;
		int st=road[s[i]];
		if(s[i]<=200000)ans++;
		tag[st]=1;
		road[s[i]]=map[road[s[i]]];
		int x=(s[i]+200000)%400000;
		int p=road[x];
		tag[p]=1;
		l=p;
		road[x]=map[road[x]];
		change(0,2*n-1,1);
		ans+=p-st-1;
		l=st+1;
		r=p-1;
		long long int tmp=find(0,2*n-1,1);
		ans-=tmp;
	}
	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