제출 #293530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293530		DystoriaX	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	209 ms	139512 KiB

shoes

#include "shoes.h"

#include <vector>
#include <algorithm>
#include <deque>
#include <bitset>
#include <iostream>

using namespace std;

int n;
int bit[200010];

void update(int x, int val){
	for(; x <= n; x += x & (-x)) bit[x] += val;
}

int query(int x){
	int ret = 0;

	for(; x; x -= x & (-x)) ret += bit[x];

	return ret;
}

int query(int l, int r){
	if(l > r) return 0;
	return query(r) - query(l - 1);
}

bitset<200010> vis;
deque<int> lf[100010], rg[100010];

long long count_swaps(vector<int> s) {
	n = s.size();

	int pos = 0;
	for(auto &k : s){
		if(k > 0) rg[k].emplace_back(++pos);
		else lf[-k].emplace_back(++pos);

		update(pos, 1);
	}

	long long ans = 0;
	for(int i = 1; i <= n; i++){
		// cerr << i << "\n";
		if(vis[i]) continue;

		vis[i] = true;

		if(s[i - 1] < 0){
			int idx = -s[i - 1];
			
			lf[idx].pop_front();
			int nxt = rg[idx].front(); rg[idx].pop_front();

			ans += query(i + 1, nxt - 1);

			update(nxt, -1);

			vis[nxt] = true;
		} else {
			int idx = s[i - 1];

			rg[idx].pop_front();
			int nxt = lf[idx].front(); lf[idx].pop_front();

			ans += query(i, nxt - 1);

			update(nxt, -1);

			vis[nxt] = true;
		}

		// cerr << i << " " << ans << "\n";

		update(i, 0);
	}

	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