Submission #1290814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290814		julia_08	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	45 ms	15404 KiB

shoes

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

using ll = long long;

using namespace std;

const int MAXN = 2e5 + 10;

int bit[MAXN], ind[MAXN];

int l[MAXN][2];

vector<int> pos[MAXN][2];

int n;

void bit_add(int pos, int x){
	for(int i=pos; i<=(2 * n); i+=(i&-i)){
		bit[i] += x;
	}
}

int bit_query(int pos){

	int sum = 0;

	for(int i=pos; i>0; i-=(i&-i)){
		sum += bit[i];
	}

	return sum;

}

ll count_swaps(vector<int> s){

	n = (int) s.size() / 2;

	for(int i=0; i<(2 * n); i++){
		if(s[i] < 0){
			pos[-s[i]][0].push_back(i + 1);
		} else pos[s[i]][1].push_back(i + 1);
	}

	vector<pair<int, int>> aux;

	ll ans = 0;

	for(int i=1; i<=n; i++){

		for(int j=0; j<pos[i][0].size(); j++){

			int l = pos[i][0][j], r = pos[i][1][j];

			if(l > r){
				swap(l, r);
				ans ++;
			}

			aux.push_back({l, r});

		}

	}

	sort(aux.begin(), aux.end());

	for(int i=1; i<=n; i++){
		ind[aux[i - 1].first] = 2 * i;
		ind[aux[i - 1].second] = 2 * i + 1;
	}

	for(int i=(2 * n); i>=1; i--){
		ans += bit_query(ind[i]);
		bit_add(ind[i], 1);
	}

	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