Submission #423451

#	Time	Username	Problem	Language	Result	Execution time	Memory
423451		Jasiekstrz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	111 ms	20624 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N=2e5;
const int PP=3e5;
vector<int> cup[2*N+10];
bool vis[N+10];
int pot;
int tree[2*PP+10];
void add_t(int l,int r,long long c)
{
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			tree[l++]+=c;
		if(r%2==0)
			tree[r--]+=c;
	}
	return;
}
long long read_t(int x)
{
	long long ans=0;
	for(x+=pot-1;x>0;x/=2)
		ans+=tree[x];
	return ans;
}
long long count_swaps(vector<int> s)
{
	int n=s.size();
	long long ans=0;
	for(int i=n-1;i>=0;i--)
		cup[N+s[i]].push_back(i+1);
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=n;i++)
		tree[pot+i-1]=i-1;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])
			continue;
		int val=s[i-1];
		int j=cup[N-val].back();
		//cerr<<val<<" "<<i<<" "<<j<<"\n";
		cup[N+val].pop_back();
		cup[N-val].pop_back();
		vis[i]=vis[j]=true;
		ans+=read_t(j);
		if(val<0)
			ans--;
		add_t(i,pot,-1);
		add_t(j,pot,-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