제출 #1160685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160685		hyakup	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	196 ms	274024 KiB

shoes

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

#define ll long long

ll count_swaps( vector<int> v ) {
	int n = v.size();

	queue<int> fila[2*(n + 1)];

	int cont = 1;
	ll resp = 0;

	vector<int> pos(n);

	for( int i = 0; i < n; i++ ){
		int t = (( v[i] > 0 ) ? 1 : 0 );
		if( fila[2*abs(v[i]) + 1 - t ].empty() ){
			pos[i] = cont;
			cont += 2;
			fila[2*abs(v[i]) + t].push(i);
			if( t == 1 ) resp++;
		}
		else{
			int outro = fila[2*abs(v[i]) + 1 - t].front();
			fila[2*abs(v[i]) + 1 - t].pop();

			pos[i] = pos[outro] + 1;
		}
	}

	vector<ll> bit(n + 1);

	auto update = [&]( int id, int val ){
		for( int i = id; i < bit.size(); i += i&-i ) bit[i] += val;
	};

	auto query = [&]( int id ){
		int sum = 0;
		for( int i = id; i > 0; i -= i&-i ) sum += bit[i];
		return sum;
	};

	for( int i = 0; i < n; i++ ){
		resp += i - query(pos[i]);
		update(pos[i], 1);
	}

	return resp;
}

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