Submission #147052

#	Time	Username	Problem	Language	Result	Execution time	Memory
147052		gs18115	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	158 ms	73716 KiB

shoes

#include"shoes.h"
#include<queue>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf=1e18;
struct fenwick
{
	ll dat[200010];
	inline void FI(int x,int p)
	{
		for(x++;x<200010;x+=x&-x)
			dat[x]+=p;
		return;
	}
	inline ll FS(int x)
	{
		ll ans=0;
		for(x++;x>0;x=x&x-1)
			ans+=dat[x];
		return ans;
	}
}FT;
queue<int>v[100010];
long long count_swaps(vector<int>s)
{
	ll ans=0;
	int n=s.size()/2;
	int i;
	for(i=0;i<n*2;i++)
	{
		FT.FI(i,1);
		if(s[i]>0)
			v[s[i]].push(i);
	}
	vector<pi>V;
	for(i=0;i<n*2;i++)
	{
		if(s[i]<0)
		{
			int t=v[-s[i]].front();
			v[-s[i]].pop();
			if(i<t)
				V.eb(i,t);
			else
				V.eb(t,i);
		}
	}
	sort(all(V));
	for(i=0;i<n;i++)
	{
		int q=V[i].fi;
		int t=V[i].se;
		if(s[q]>0)
			ans++;
		FT.FI(t,-1);
		ans+=FT.FS(t)-FT.FS(q);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'll fenwick::FS(int)':
shoes.cpp:25:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   for(x++;x>0;x=x&x-1)
                   ~^~

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