Submission #1230420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230420		altern23	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	42 ms	15172 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])].push_back(i);
		else kanan[s[i]].push_back(i);
	}
	
	for(int i = 0; i <= N; i++){
		reverse(kiri[i].begin(), kiri[i].end());
		reverse(kanan[i].begin(), kanan[i].end());
	}
	vector<int> vis(2 * 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 || vis[i]) continue;
		vis[i] = 1, vis[kiri[abs(s[i])].back()] = 1;
		ans += abs(bit.get(kiri[abs(s[i])].back()) - bit.get(i)) - (kiri[abs(s[i])].back() < i);
		if(kiri[s[i]].back() < i){
			bit.upd(kiri[s[i]].back() + 1, 1);
			bit.upd(i, -1);
		}
		else{
			bit.upd(i + 1, -1);
			bit.upd(kiri[s[i]].back() + 1, 1);
		}
		kiri[abs(s[i])].pop_back();
		kanan[abs(s[i])].pop_back();
	}
	
	return ans;
}

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