제출 #536372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536372		zggf	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	154 ms	143916 KiB

shoes

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

using namespace std;

vector<ll> tree;
int treeSize;

int pot(int x){
	int tmp = 1;
	while(x){
		x/=2;
		tmp*=2;
	}
	return tmp;
}

void update(int a){
	a+=treeSize;
	while(a){
		tree[a]++;
		a/=2;
	}
}

int qur(int a, int b){
	a+=treeSize;
	b+=treeSize;
	int out = tree[a];
	if(b!=a) out+=tree[b];
	while(a/2!=b/2){
		if(a%2==0) out+=tree[a+1];
		if(b%2==1) out+=tree[b-1];
		a/=2; 
		b/=2;
	}
	return out;
}

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	vector<queue<int>> tab(n+10);
	vector<int> ile(n+10);
	vector<int> ile2(n+10);
	treeSize = pot(n+3);
	tree.resize(treeSize*2+1);
	ll wyn = 0;
	for(int i = 0; i < (int)s.size(); i++){
		if(s[i]<0){
			if(ile2[-s[i]]>0){
				ile2[-s[i]]--;
				tab[-s[i]].push(i);
				s[i] = -s[i];
			}else{
				ile[-s[i]]++;
			}
		}else{
			if(ile[s[i]]==0){
				wyn++;		
				ile2[s[i]]++;
				s[i] = -s[i];
			}else{
				tab[s[i]].push(i);
				ile[s[i]]--;
			}
		}
	}
	for(int i = 0; i < (int)s.size(); i++){
		if(s[i]<0){
			int x = tab[-s[i]].front();
			tab[-s[i]].pop();
			wyn+=x-i-1;
			wyn-=qur(i, x);
			update(x);
		}
	}
	return wyn;
}

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