제출 #1290701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290701		Sofiatpc	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	76 ms	13500 KiB

shoes

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

using namespace std;

const int MAXN = 2*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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15