Submission #1035970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035970		ArthuroWich	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	294 ms	34488 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long arr[200005], seg[4*200005];
void build(long long n, long long l, long long r) {
	if (l == r) {
		seg[n] = arr[l];
	} else {
		long long 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(long long n, long long l, long long r, long long i, long long v) {
	if (l == r) {
		seg[n] = v;
	} else {
		long long 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];
	}
}
long long query(long long n, long long l, long long r, long long a, long long b) {
	if (b < l || r < a) {
		return 0;
	} else if (a <= l && r <= b) {
		return seg[n];
	} else {
		long long 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) {
	long long n = s.size(), ans = 0;
	vector<long long> vis(n, 0);
	map<long long, vector<long long>> num;
	for (long long 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 (long long i = 0; i < n; i++) {
		if (vis[i]) {
			continue;
		}
		long long co = 0, ind = -1;
		long long 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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15