제출 #1266685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266685		cmiuc	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	164 ms	179284 KiB

shoes

#include <iostream>
#include <queue>
#include <algorithm>
#include "shoes.h"

using namespace std;
queue<int> Q[1<<18];
int ft[1<<18];

void add(int i, int v){
	for (;i < (1<<18);i += i & -i)
		ft[i] += v;
}

int get(int i, int Ans = 0){
	for (; i > 0; i -= i & -i)
		Ans += ft[i];
	return Ans;
}

int get(int l, int r, int c){
	c = get(r) - get(l - 1);
	add(l, 1);
	return c;
}


long long count_swaps(vector<int> v){
	long long Ans = 0;
	int n = v.size() / 2;

	for (int i=0;i<n + n;i++){
		if (v[i] < 0){
			if (Q[-v[i] + n + 1].size() == 0)
				Q[v[i] + n + 1].push(i + 1), add(i + 1, 1);
			else
				Ans += get(Q[-v[i] + n + 1].front(), i, 0), Q[-v[i] + n + 1].pop();
		}
		else{
			if (Q[-v[i] + n + 1].size() == 0)
				Q[v[i] + n + 1].push(i + 1), add(i + 1, 1);
			else
				Ans += get(Q[-v[i] + n + 1].front(), i, 0) - 1, Q[-v[i] + n + 1].pop();
		}
	}
	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