Submission #1230413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230413		altern23	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

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

#define ll long long

struct BIT{
	ll N;
	vector<ll> bit;
	BIT(ll _n){
		N = _n;
		bit.resize(N + 5);
	}
	
	void upd(ll idx, ll val){
		idx++;
		for(; idx <= N; idx += idx & -idx) bit[idx] += val;
	}
	ll get(ll idx){
		idx++;
		ll ans = 0;
		for(; idx >= 1; idx -= idx & -idx) ans += bit[idx];
		return ans;
	}
	ll query(ll l, ll r) { return get(r) - get(l - 1); }
};

long long count_swaps(vector<int> s) {
	int N = (int)s.size() / 2;
	vector<int> kiri(N + 5), kanan(N + 5);
	for(int i = 0; i < 2 * N; i++){
		if(s[i] < 0) kiri[abs(s[i])] = i;
		else kanan[s[i]] = i;
	}
	
	vector<int> vis(N + 5);
	int ans = 0;
	
	BIT bit(2 * N);
	for(int i = 0; i < 2 * N; i++) bit.upd(i, 1);
	for(int i = 0; i < 2 * N; i++){
		if(s[i] < 0) continue;
		if(vis[abs(s[i])]) continue;
		ans += abs(bit.get(kanan[abs(s[i])]) - bit.get(kiri[abs(s[i])]));
		vis[abs(s[i])] = 1;
		if(kiri[s[i]] < i){
			bit.upd(kiri[s[i]] + 1, 1);
			bit.upd(i, -1);
		}
		else{
			bit.upd(i + 1, -1);
			bit.upd(kiri[s[i]] + 1, 1);
		}
	}
	
	return ans;
}

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