Submission #1216094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216094		santi3223	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	402 ms	153864 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define ll long long
#define vl vector<ll>
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

vl t;
vl arr;

void build(ll i, ll l, ll r){
	if(l == r){
		t[i] = 1;
		return;
	}
	ll mid = (l+r)/2;
	build(2*i+1, l, mid);
	build(2*i+2, mid+1, r);
	t[i] = t[2*i+1]+t[2*i+2];
}

void update(ll i, ll l, ll r, ll p, ll v){
	if(l == r){
		t[i] = v;
		return;
	}
	ll mid = (l+r)/2;
	if(p <= mid){
		update(2*i+1, l, mid, p, v);
	}
	else{
		update(2*i+2, mid+1, r, p, v);
	}
	t[i] = t[2*i+1]+t[2*i+2];
}

ll query(ll i, ll tl, ll tr, ll ql, ll qr){
	if(tr < ql || qr < tl){
		return 0;
	}
	if(ql <= tl && tr <= qr){
		return t[i];
	}
	ll mid = (tl+tr)/2;
	return query(2*i+1, tl, mid, ql, qr)+query(2*i+2, mid+1, tr, ql, qr);
}

ll count_swaps(vector<int> S){
	ll n = S.size();
	map<ll, deque<ll>> mp;
	arr = vl(n);
	ff(i, 0, n){
		arr[i] = S[i];
		mp[arr[i]].pb(i);
	}
	t = vl(4*n, 0);
	build(0, 0, n-1);
	vb ok(n, true);
	ll c = 0;
	ff(i, 0, n){
		if(ok[i]){
			ll other = mp[-(arr[i])].front();
			mp[-(arr[i])].pop_front();
			ok[other] = false;
			if(arr[i] > 0){
				c++;
			}
			mp[arr[i]].pop_front();
			ll suma = query(0, 0, n-1, i, other);
			c += suma-query(0, 0, n-1, i, i)-query(0, 0, n-1, other, other);
			update(0, 0, n-1, i, 2);
			update(0, 0, n-1, other, 0);
		}
	}
	return c;
}
/*
int main(){
	ll n;
	cin >> n;
	vector<int> A(n);
	ff(i, 0, n){
		cin >> A[i];
	}
	cout << count_swaps(A);
}
*/

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