Submission #825749

#	Time	Username	Problem	Language	Result	Execution time	Memory
825749		RakhimovAmir	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	25 ms	7504 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;
int t[4 * N], sum[4 * N], p = 0;
vector <int> S;
void build (int x, int tl, int tr){
	if (tl == tr){
		t[x] = tl;
	}
	else{
		int mid = (tl + tr)/2;
		build(x * 2, tl, mid);
		build(x * 2 + 1, mid + 1, tr);
		t[x] = t[2 * x] + t[2 * x + 1];
	}
}
void update(int l, int r, int x, int tl, int tr){
	if (l > r){
		return ;
	}
	else if (l == tl && r == tr){
		sum[x]++;
	}
	else{
		//cout << l << " " << r << " " << x << " " << tl << " " << tr << "\n";
		int tmid = (tl + tr)/2;
		update(l, min(tmid, r), x * 2, tl, tmid);
		update(max(l, tmid + 1), r, x * 2 + 1, tmid + 1, tr);
	}
}
int get(int num, int x, int tl, int tr){
	if (tl == tr){
		p+=sum[x];
		return t[x] + sum[x];
	}
	else{
		p+=sum[x];
		int tmid = (tl + tr)/2;
		if (num > tmid)
			return get(num, x * 2 + 1, tmid + 1, tr) + sum[x];
		else
			return get(num, x * 2, tl, tmid) + sum[x];
	}
}
long long count_swaps(vector<int> s) {
	int ans = 0, n = s.size();
	map <int, deque <int>> mp;
	int used[n];
	build(1, 0, n - 1);
	for (int i = 0 ; i < n ; i++){
		used[i] = 0;
		//cout << get(i, 1, 0, n - 1) << "\n";
		mp[s[i]].push_back(i);
	}
	for (int i = 0 ; i < n ; i++){
		if (used[i])
			continue ;
		int cur1 = i, cur2 = mp[s[i] * -1][0];
		mp[s[i] * -1].pop_front();
		mp[s[i]].pop_front();
		//cout << get(cur1, 1, 0, n - 1) << " " << get(cur2, 1, 0, n - 1) << "\n";
		ans+=max(get(cur1, 1, 0, n - 1), get(cur2, 1, 0, n - 1)) - min(get(cur1, 1, 0, n - 1), get(cur2, 1, 0, n - 1)) - 1;
		update(min(cur1, cur2), max(cur1, cur2), 1, 0, n - 1);
		//cout << get(cur1, 1, 0, n - 1) << " " << get(cur2, 1, 0, n - 1) << "\n";
		used[cur1] = 1;
		used[cur2] = 1;
		if (s[i] > 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