Submission #599676

#	Time	Username	Problem	Language	Result	Execution time	Memory
599676		OrazB	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	273 ms	202920 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define N 4000005
#define wr cout << "Continue debugging\n";
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
using namespace std;

ll t[N], s[N], vis[N];
vector <int> a, v1[N], v2[N];

void build(int l, int r, int idx){
	if (l == r){t[idx] = 1; return;}
	int md = (l + r) / 2;
	build(l, md, idx*2);
	build(md+1, r, idx*2+1);
	t[idx] = t[idx*2] + t[idx*2+1];
}
ll sum(int a, int b, int l, int r, int idx){
	if (r < a or l > b) return 0;
	if (l >= a and r <= b) return t[idx];
	int md = (l + r) / 2;
	return sum(a, b, l, md, idx*2) + sum(a, b, md+1, r, idx*2+1);
}
void upd(int nd, int l, int r, int idx){
	int md = (l + r) / 2;
	if (l == r){t[idx] = 0; return;}
	if (nd <= md) upd(nd, l, md, idx*2);
	else upd(nd, md+1, r, idx*2+1);
	t[idx] = t[idx*2] + t[idx*2+1];
}
ll count_swaps(vector <int> a){
	ll n = a.size(), ans = 0;
	for (int i = 0; i < n; i++){
		if (a[i] < 0) v1[-a[i]].pb(i);
		else v2[a[i]].pb(i);
	}
	build(0, n-1, 1);
	for (int i = 1; i <= n; i++){
		reverse(v1[i].begin(), v1[i].end());
		reverse(v2[i].begin(), v2[i].end());
	}
	for (int i = 0; i < n; i++){
		if (vis[i]) continue;
		int idx = 0;
		if (a[i] < 0){
			idx = v2[-a[i]].back();
			ans += sum(i+1, idx-1, 0, n-1, 1);
		}else{
			idx = v1[a[i]].back();
			ans += sum(i+1, idx-1, 0, n-1, 1)+1;
		}
		v2[abs(a[i])].pop_back();
		v1[abs(a[i])].pop_back();
		vis[idx] = 1;
		upd(idx, 0, n-1, 1);
	}
	return ans;
}
// int main ()
// {
// 	int n1;
// 	cin >> n1;
// 	for (int i = 1; i <= n1; i++) cin >> s[i], a.pb(s[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