제출 #1309564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309564		husseinjuanda	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	213 ms	24688 KiB

shoes

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

int n;

vector<int> fen;
void update(int i, int v){
	for(; i <= n; i+= i & -i) fen[i] += v;
}

int ans(int i){
	if(i == 0) return 0;
	int ns = 0;
	for(; i >= 1; i -= i & -i) ns += fen[i];
	return ns;
}

int query(int l, int r){
	return ans(r) - ans(l-1);
}

long long count_swaps(std::vector<int> s) {
	n = s.size();
	fen.resize(n+1);
	map<int, vector<int>> m;
	long long ns = 0;
	for(int i = s.size()-1; i >= 0; i--){
		m[s[i]].push_back(i);
	}
	for(int i = 0; i < s.size(); i++){
		if(query(i+1, i+1) == 1) continue;
		if(s[i] < 0){
			m[s[i]].pop_back();
			int r = m[-s[i]].back();
			int l = i+1;
			m[-s[i]].pop_back();
			int j = query(l+1, r+1);
			ns += r-l - j;
			update(r+1, 1);
		}else{
			m[s[i]].pop_back();
			int r = m[-s[i]].back();
			int l = i;
			m[-s[i]].pop_back();
			int j = query(l+1, r+1);
			ns += r-l - j;
			update(r+1, 1);
		}
	}
	return ns;
}

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