Submission #1290700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290700		Sofiatpc	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	32 ms	13164 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;
vector<int> idl[MAXN], idr[MAXN];
int bit[MAXN], n;

void update(int i){
	for(; i <= n; i += i&-i)
		bit[i] += 1;
}

int query(int i){
	if(i < 1)return 0;
	int resp = 0;
	for(; i > 0; i -= i&-i)
		resp += bit[i];
	return resp;
}

long long count_swaps(vector<int> s) {
	n = s.size();
	for(int i = 1; i <= n; i++)bit[i] = 0;

	for(int i = s.size(); i >= 1; i--){
		if(s[i-1] < 0)idl[-s[i-1]].push_back(i);
		else idr[s[i-1]].push_back(i);
	}

	long long ans = 0;
	for(int i = 1; i <= n; i++){
		if(query(i)-query(i-1) == 1)continue;
		long long pos = i+query(n)-query(i);
		update(i);

		if(s[i-1] > 0){//right
			long long nxt = idl[s[i-1]].back();
			update(nxt);
			nxt = nxt+query(n)-query(nxt);
			ans += nxt-pos;
		}else{//left
			long long nxt = idr[-s[i-1]].back();
			update(nxt);
			nxt = nxt+query(n)-query(nxt);
			ans += nxt-pos-1;
		}
		idl[abs(s[i-1])].pop_back(); idr[abs(s[i-1])].pop_back();
	}
	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15