Submission #304727

#	Time	Username	Problem	Language	Result	Execution time	Memory
304727		kjain_1810	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	273 ms	141444 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>

typedef long long ll;
using namespace std;

const int N = 1e5 + 5;

int n;
ll segt[8 * N];
queue<int>vec[2 * N];

inline int lt(int x){return 2 * x;}
inline int rt(int x){return 2 * x + 1;}

void upd(int nd, int s, int e, int idx) {
	if(s > idx || e < idx)
		return;
	if(s == e) {
		segt[nd] += 1;
		return;
	}
	int m = (s + e) / 2;
	upd(lt(nd), s, m, idx);
	upd(rt(nd), m + 1, e, idx);
	segt[nd] = segt[lt(nd)] + segt[rt(nd)];
}

ll query(int nd, int s, int e, int l, int r) {
	if(s > r || e < l)
		return 0;
	if(s >= l && e <= r)
		return segt[nd];
	int m = (s + e) / 2;
	return query(lt(nd), s, m, l, r) + query(rt(nd), m + 1, e, l, r);
}

long long count_swaps(vector<int> s) {
	ll ans = 0;
	n = s.size();
	for(int a = 0; a < n; a++){
		s[a] += n / 2;
		vec[s[a]].push(a);
	}
	for(int a = 0; a < n; a++) {
		if(query(1, 1, n, a, a) == 1)
			continue;
		int target;
		if(s[a] > n)
			target = (-(s[a] - n / 2) + n / 2);
		else
			target = (-(s[a] - n / 2) + n / 2);
		int idx = vec[target].front();
		vec[target].pop();
		vec[s[a]].pop();
		ll toadd;
		if(s[a] < target)
			toadd = (idx - a - 1 - query(1, 1, n, a, idx));
		else
			toadd = (idx - a - query(1, 1, n, a, idx));
		ans += toadd;
		// printf("%d %d %d %d %lld\n", a, s[a], target, idx, toadd);
		upd(1, 1, n, idx);
	}
	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