Submission #438071

#	Time	Username	Problem	Language	Result	Execution time	Memory
438071		ToroTN	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	165 ms	21448 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
#include "shoes.h"
long long n,cnt=0,a[200005],seg[800005];
vector<long long> v[100005][2];
vector<pair<long long,long long> > p;
void build(long long tree,long long st,long long ed)
{
	long long md=(st+ed)/2;
	if(st==ed)
	{
		seg[tree]=a[st];
		return;
	}
	build(2*tree,st,md);
	build(2*tree+1,md+1,ed);
	seg[tree]=seg[2*tree]+seg[2*tree+1];
}
void update(long long tree,long long st,long long ed,long long idx,long long val)
{
	long long md=(st+ed)/2;
	if(st==ed)
	{
		seg[tree]=val;
		return;
	}
	if(idx<=md)
	{
		update(2*tree,st,md,idx,val);
	}else
	{
		update(2*tree+1,md+1,ed,idx,val);
	}
	seg[tree]=seg[2*tree]+seg[2*tree+1];
}
long long query(long long tree,long long st,long long ed,long long l,long long r)
{
	long long md=(st+ed)/2;
	if(st>r||ed<l)
	{
		return 0;
	}
	if(st>=l&&ed<=r)
	{
		return seg[tree];
	}
	return query(2*tree,st,md,l,r)+query(2*tree+1,md+1,ed,l,r);
}
long long count_swaps(std::vector<int> s) {
	n=s.size();
	for(int i=0;i<n;i++)
	{
		if(s[i]>0)
		{
			v[s[i]][0].push_back(i+1);
		}else
		{
			v[-s[i]][1].push_back(i+1);
		}
	}
	for(int i=1;i<=n/2;i++)
	{
		for(int j=0;j<v[i][0].size();j++)
		{
			if(v[i][0][j]<v[i][1][j])
			{
				cnt+=1;
				p.push_back(make_pair(v[i][0][j],v[i][1][j]));
			}else
			{
				p.push_back(make_pair(v[i][1][j],v[i][0][j]));
			}
		}
	}
	sort(p.begin(),p.end());
	for(int i=1;i<=n;i++)
	{
		a[i]=1;
	}
	//printf("%lld\n",cnt);
	//printf("%lld\n",n);
	build(1,1,n);
	for(int i=0;i<p.size();i++)
	{
		//printf("%lld %lld\n",p[i].first,p[i].second);
		//printf("%lld\n",p[i].second);
		cnt+=query(1,1,n,p[i].first+1,p[i].second)-1;
		//printf("%lld\n",cnt);
		update(1,1,n,p[i].second,0);
		/*for(int j=1;j<=n;j++)
		{
			printf("%lld ",query(1,1,n,j,j));
		}
		printf("\n");*/
	}
	return cnt;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int j=0;j<v[i][0].size();j++)
      |               ~^~~~~~~~~~~~~~~
shoes.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i=0;i<p.size();i++)
      |              ~^~~~~~~~~

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