제출 #954626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954626		waldi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	285 ms	42492 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

struct przedzialowiec{
	int N;
	vector<int> t;
	przedzialowiec(int n){
		for(N = 1; N < n;) N <<= 1;
		t.resize(N<<1, 0);
	}
	void dodaj(int poz, int wart){
		for(poz += N; poz; poz >>= 1) t[poz] += wart;
	}
	int suma(int p, int k){
		int ret = 0;
		for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
			if(p&1) ret += t[p++];
			if(k&1) ret += t[--k];
		}
		return ret;
	}
};

ll count_swaps(vector<int> wej){
	int n = ssize(wej)>>1;
	
	unordered_map<int, set<int>> mapa;
	REP(i, 2*n) mapa[wej[i]].emplace(i);
	
	ll wyn = 0ll;
	set<int> istnieje;
	przedzialowiec prz(n<<1);
	REP(i, n<<1) prz.dodaj(i, 1), istnieje.emplace(i);
	while(ssize(istnieje)){
		int t = *istnieje.begin();
		int wart = wej[t];
		int poz = *mapa[-wart].begin();
		
		wyn += prz.suma(0, poz-1);
		if(wart < 0) --wyn;
		
		prz.dodaj(t, -1);
		prz.dodaj(poz, -1);
		
		mapa[wart].erase(t);
		mapa[-wart].erase(poz);
		
		istnieje.erase(t);
		istnieje.erase(poz);
	}
	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