Submission #1035969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035969		ArthuroWich	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	233 ms	28928 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int arr[200005], seg[4*200005];
void build(int n, int l, int r) {
	if (l == r) {
		seg[n] = arr[l];
	} else {
		int m = (l+r)/2;
		build(2*n, l, m);
		build(2*n+1, m+1, r);
		seg[n] = seg[2*n] + seg[2*n+1];
	}
}
void update(int n, int l, int r, int i, int v) {
	if (l == r) {
		seg[n] = v;
	} else {
		int m = (l+r)/2;
		if (l <= i && i <= m) {
			update(2*n, l, m, i, v);
		} else {
			update(2*n+1, m+1, r, i, v);
		}
		seg[n] = seg[2*n] + seg[2*n+1];
	}
}
int query(int n, int l, int r, int a, int b) {
	if (b < l || r < a) {
		return 0;
	} else if (a <= l && r <= b) {
		return seg[n];
	} else {
		int m = (l+r)/2;
		return query(2*n, l, m, a, b) + query(2*n+1, m+1, r, a, b);
	}
}
long long count_swaps(vector<int> s) {
	int n = s.size(), ans = 0;
	vector<int> vis(n, 0);
	map<int, vector<int>> num;
	for (int i = 0; i < n; i++) {
		num[s[i]].push_back(i);
		arr[i] = 1;
	}
	for (auto c : num) {
		reverse(num[c.first].begin(), num[c.first].end());
	}
	build(1, 0, n-1);
	for (int i = 0; i < n; i++) {
		if (vis[i]) {
			continue;
		}
		int co = 0, ind = -1;
		int j = s[i]*-1;
		ind = num[j].back();
		num[s[i]].pop_back();
		num[j].pop_back();
		co = query(1, 0, n-1, i, ind)-2;
		vis[i] = 1;
		vis[ind] = 1;
		update(1, 0, n-1, i, 0);
		update(1, 0, n-1, ind, 0);
		ans += co;
		if (j < 0) {
			ans++;
		}
	}
	return ans;
}

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