Submission #1237641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237641		lalig777	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	87 ms	21180 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <queue>
using namespace std;

vector<int>closest;
vector<long long>added(1e6, 0);
vector<bool>puesto;
int n;

void find_next(vector<int>& s){
	unordered_map<int, priority_queue<int> >mapa;
	for (int i=0; i<n; i++){
		int siz=s[i];
		if (mapa.find(-siz)!=mapa.end() and mapa[-siz].size()>0){
			int ind=-mapa[-siz].top();
			mapa[-siz].pop();
			closest[ind]=i;
			closest[i]=ind;
		}else mapa[siz].push(-i);
	}return;
}

long long find_pos(int p, int l, int r, int x){
	if (l==r) return added[p];
	int m=(l+r)/2;
	if (x<=m) return added[p]+find_pos(p*2, l, m, x);
	else return added[p]+find_pos(p*2+1, m+1, r, x);
}

void add(int p, int l, int r, int a, int b){
	if (a<=l && b>=r){
		added[p]++;
		return;
	}else if (b<l || a>r) return;
	int m=(l+r)/2;
	add(p*2, l, m, a, b);
	add(p*2+1, m+1, r, a, b);
	return;
}


long long count_swaps(vector<int> s) {
	n=s.size();
	closest.assign(n, -1);
	puesto.assign(n, false);
	find_next(s);
	//for (int i=0; i<n; i++) cout<<closest[i]<<' ';
	long long int ans=0;
	for (int i=0; i<n; i++){
		if (puesto[i]==true) continue;
		int ind=closest[i];
		puesto[i]=true;
		puesto[ind]=true;
		int posi=i+find_pos(1, 0, n-1, i);
		int posind=ind+find_pos(1, 0, n-1, ind);
		//cout<<posi<<' '<<posind<<endl;
		ans=ans+posind-posi;
		if (s[i]<0) ans--;
		if (i+1<=ind-1) add(1, 0, n-1, i+1, ind-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