Submission #169784

#	Time	Username	Problem	Language	Result	Execution time	Memory
169784		arthur_nascimento	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	236 ms	140408 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define debug printf
#define ll long long
#define maxn 200200
queue<int> st[maxn];

int par[maxn];
int foi[maxn];
int T[maxn];

void upd(int idx,int val){
	idx++;
	while(idx < maxn){
		T[idx] += val;
		idx += (idx&-idx);
	}
}

int get(int idx){ //debug("get %d\n",idx);
	idx++;;
	int r = 0;
	while(idx){
		r += T[idx];
		idx -= (idx&-idx);
	}
	//debug("-> %d\n",r);
	return r;
}

long long count_swaps(std::vector<int> S){

	int n = S.size();
	
	ll ans = 0;

	for(int i=0;i<n;i++){
		//debug("i %d %d\n",i,S[i]);
		int sz = abs(S[i]);
		if(st[sz].size() > 0 && S[st[sz].front()] == - S[i]){
			if(S[i] < 0) ans++;
			par[st[sz].front()] = i;
			//debug("%d - %d\n",st[sz].front(),i);
			st[sz].pop();
		}
		else {
			st[sz].push(i);
			//debug("add\n");
		}
	}
	
	
	
	for(int i=0;i<n;i++) upd(i,1);
	
	for(int i=0;i<n;i++) if(!foi[i]){
		int u = par[i];
		ans += get(u-1) - get(i);
		upd(u,-1);
		foi[u] = 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