Submission #468073

#	Time	Username	Problem	Language	Result	Execution time	Memory
468073		gs18103	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	32 ms	5028 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define fi first
#define se second
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

class BinaryIndexedTree {
	vector <int> tree;
	int sz;
public:
	void Init(int n) {
		sz = n;
		tree.resize(n+1);
	}
	void update(int i, int val) {
		while(i <= sz) {
			tree[i] += val;
			i += (i & -i);
		}
	}
	int cal(int l, int r) {
		int ret = 0;
		while(r > 0) {
			ret += tree[r];
			r -= (r & -r);
		}
		l--;
		while(l > 0) {
			ret -= tree[l];
			l -= (l & -l);
		}
		return ret;
	}
};

ll count_swaps(vector<int> s) {
	int n = s.size() / 2;
	vector <int> pos(n + 1, -1), pre(2*n);
	
	for(int i = 0; i < 2 * n; i++) {
		if(pos[abs(s[i])] == -1) {
			pre[i] = -1;
			pos[abs(s[i])] = i;
		}
		else {
			pre[i] = pos[abs(s[i])];
			pos[abs(s[i])] = -1;
		}
	}
	BinaryIndexedTree BIT;
	BIT.Init(2*n);
	ll ans = 0;
	for(int i = 2 * n - 1; i >= 0; i--) {
		if(pre[i] == -1) continue;
		ans += i - pre[i] - BIT.cal(pre[i] + 1, i + 1);
		if(s[i] > 0) ans--;
		BIT.update(pre[i] + 1, 1);
	}
	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