Submission #832998

#	Time	Username	Problem	Language	Result	Execution time	Memory
832998		Halym2007	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	343 ms	36380 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define pb push_back
map <int, vector <int>> m;
map <int, vector <int>> mp;
int st[524287];
map <int, bool> vis;
int tap (int ind, int x, int y, int l, int r) {
	if (l > y or x > r) {
		return 0;
	}
	if (l <= x and y <= r) {
		return st[ind];
	}
	return tap (ind * 2 + 1, x, (x + y) / 2, l, r) + tap (ind * 2 + 2, (x + y) / 2 + 1, y, l, r);
}

void update (int ind, int l, int r, int x) {
	if (l > x or x > r) return;
	if (l == r) {
		st[ind]++;
		return;
	}
	update (ind * 2 + 1, l, (l + r) / 2, x);
	update (ind * 2 + 2, (l + r) / 2 + 1, r, x);
	st[ind] = st[ind * 2 + 1] + st[ind * 2 + 2];
}

ll count_swaps(vector<int> S) {
	int n = S.sz;
	ll jogap = 0;
	for (int i = n - 1; i > 0; i--) {
		if (S[i] > 0)
			m[S[i]].pb (i);
		else
			mp[S[i]].pb (i);
	}
	for (int i = 0; i < n; ++i) {
		if (vis[i]) {
			continue;
		}
		// r we l saylamaly
		int l = i, r;
		vis[i] = 1;
		if (S[i] < 0) {
			r = m[-S[i]].back();
			while (vis[r]) {
				m[-S[i]].pop_back();
				r = m[-S[i]].back();
			}
			vis[r] = 1;
			m[-S[i]].pop_back();
		}
		else {
			r = mp[-S[i]].back();
			while (vis[r]) {
				mp[-S[i]].pop_back();
				r = mp[-S[i]].back();
			}
			vis[r] = 1;
			mp[-S[i]].pop_back();
		}
		int jog = r - l - 1;
		if (S[i] > 0) jog++;
			jog -= tap (0, 0, n - 1, i, r);
		update (0, 0, n - 1, r);
		jogap += (ll)jog;
	}
	return jogap;
}


// int main() {
// 	freopen("input1.txt", "r", stdin);
// 	int n;
// 	cin >> n;
// 	vector<int> S(2 * n);
// 	for (int i = 0; i < 2 * n; i++)
// 		cin >> S[i];
// 	ll result = count_swaps(S);
// 	cout << result << '\n';
// 	return 0;
// }

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