Submission #1030069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030069		Dan4Life	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	440 ms	157420 KiB

shoes

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

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;

const int mxN = (int)2e5+10;
int n, fen[mxN];
void upd(int x, int v){
	for(++x;x<mxN; x+=x&-x)fen[x]+=v;
}

int sum(int x){
	int s = 0;
	for(++x;x>0;x-=x&-x) s+=fen[x];
	return s;
}

map<int,deque<int>> v;
ll count_swaps(vector<int> a) {
	n = sz(a); v.clear(); ll ans = 0;
	set<ar2> S; S.clear();
	for(int i = 0; i < n; i++) 
		v[a[i]].pb(i), S.insert({i,a[i]});
	while(sz(S)){
		int i = (*S.begin())[0]; 
		int I = i+sum(i);
		int x = -(*S.begin())[1];
		
		int j = v[x][0];
		int J = j+sum(j);
		upd(i,-1); upd(j,-1);
		
		ans+=J-I-(x>0);
		v[x].pop_front();
		v[-x].pop_front();
		S.erase(S.begin());
		S.erase({j,a[j]});
	}
	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