Submission #1237125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237125		AMnu	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	46 ms	5300 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2e5+5;

int N, fen[MAXN];
ll ans;
pii P[MAXN];
vector <pii> L, R;

int pref(int x) {
	int sum = 0;
	for (int i=x;i;i-=i&-i) {
		sum += fen[i];
	}
	return sum;
}

void add(int x) {
	for (int i=x;i<=2*N;i+=i&-i) {
		fen[i]++;
	}
}

void ins(int x) {
	add(x);
	ans += x-pref(x);
}

ll count_swaps(vector<int> s) {
	N = s.size() / 2;
	for (int i=0;i<2*N;i++) {
		if (s[i] > 0) {
			R.push_back({s[i],i+1});
		}
		else {
			L.push_back({-s[i],i+1});
		}
	}
	sort(L.begin(),L.end());
	sort(R.begin(),R.end());
	for (int i=0;i<N;i++) {
		P[i].fi = L[i].se;
		P[i].se = R[i].se;
		if (P[i].fi > P[i].se) {
			swap(P[i].fi,P[i].se);
			ans++;
		}
	}
	sort(P,P+N);
	for (int i=0;i<N;i++) {
		ins(P[i].fi);
		ins(P[i].se);
	}
	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