Submission #609512

#	Time	Username	Problem	Language	Result	Execution time	Memory
609512		penguinhacker	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	177 ms	139384 KiB

shoes

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, ft[2*mxN+1];
queue<int> ls[mxN+1], rs[mxN+1];
bool vis[2*mxN];

void upd(int i) {
	for (++i; i<=2*n; i+=i&-i)
		++ft[i];
}

int qry(int i) {
	int r=0;
	for (++i; i; i-=i&-i)
		r+=ft[i];
	return r;
}

ll count_swaps(vector<int> s) {
	n=s.size()/2;
	for (int i=0; i<2*n; ++i) {
		if (s[i]<0)
			ls[-s[i]].push(i);
		else
			rs[s[i]].push(i);
	}
	ll ans=0;
	for (int i=0; i<2*n; ++i) {
		if (qry(i)-qry(i-1))
			continue;
		int x=abs(s[i]);
		//cout << i << " " << qry(i) << " " << qry(i-1) << endl;
		assert(ls[x].size()&&rs[x].size());
		//cout << ls[x].front() << " " << rs[x].front() << endl;
		ans+=ls[x].front()-qry(ls[x].front());
		upd(ls[x].front());
		ls[x].pop();
		ans+=rs[x].front()-qry(rs[x].front());
		upd(rs[x].front());
		rs[x].pop();
	}
	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