Submission #228901

#	Time	Username	Problem	Language	Result	Execution time	Memory
228901		monus1042	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	203 ms	31804 KiB

shoes

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

typedef long long ll;

ll ans=0;
const ll MAXS = 5e5+10;
ll BIT[MAXS];
bool vis[MAXS];
ll n;
unordered_map<ll, set<ll>> ma; //numi, original pos

void updrange(ll pos, ll delta){
	ll it=pos;
	while(it<=n){
		BIT[it] += delta;
		it += (it & -it);
	}
}

ll query(ll pos){
	ll res=0;
	while(pos > 0){
		res+=BIT[pos];
		pos -= (pos & -pos);
	}
	return res;
}

ll count_swaps(std::vector<int> s) {
	n=s.size();

	for (ll i=0; i<n; i++)
		ma[s[i]].insert(i);
	
	for (ll i=0; i<n-1; i++){
		if (vis[i]) continue;
		vis[i]=1;
		auto ff=ma[s[i]].begin();
		ma[s[i]].erase(ff);
		if (s[i]>0){
			auto fopp=ma[s[i]*-1].begin();
			ll cpos=i + query(i+1);
			ll copppos=*fopp + query(*fopp + 1);
			ll origopppos=*fopp;
			ma[s[i]*-1].erase(fopp);

			ll diff=copppos - cpos;
			ans+=diff;
			//cout<<"\t"<<diff<<' '<<cpos<<' '<<copppos<<' '<<origopppos<<endl;
			updrange(i+1, 1);
		    updrange(origopppos+1, -1);
			vis[origopppos]=1;
		}else{
			auto fopp=ma[s[i]*-1].begin();
			ll cpos=i + query(i+1);
			ll copppos=*fopp + query(*fopp + 1);
			ll origopppos=*fopp;
			ma[s[i]*-1].erase(fopp);

			ll diff=copppos - cpos - 1;
			ans+=diff;
			vis[origopppos]=1;
			if (diff>0){
				updrange(i+2, 1);
				updrange(origopppos+1, -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