Submission #1144493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144493		zhasyn	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	206 ms	274800 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll N = 2 * 1e5 + 100;
ll fen[N];
deque <ll> pos[N], neg[N];
bool was[N];
void upd(int i, int delta){
	for(; i < N; i |= (i + 1)){
		fen[i] += delta;
	}
}
ll get(ll r){
	ll res = 0;
	for(; r >= 0; r = (r &(r + 1)) - 1){
		res += fen[r];
	}
	return res;
}
long long count_swaps(std::vector<int> s) {
	ll ans = 0, last, n = (int)s.size();
	for(int i = 0; i < (int)s.size(); i++){
		if(s[i] < 0) neg[-s[i]].pb(i);
		else pos[s[i]].pb(i);
		upd(i, 1);
	}
	
	for(int i = 0; i < n; i++){
		if(was[i]) continue;
		if(s[i] < 0){
			last = pos[-s[i]].front();
			ans -= 2;
		}
		else{
			last = neg[s[i]].front();
			ans--;
		}
		pos[abs(s[i])].pop_front();
		neg[abs(s[i])].pop_front();
		
		ans += get(last);
		//cout << i << " "<< last << " " << ans << endl;
		was[last] = true;
		upd(last, -1);
		upd(i, -1);
	}
	return ans;
}
// int main(){
	// vector <int> s;
	// int n;
	// cin >> n;
	// for(int i = 0, x; i < n; i++){
		// cin >> x;
		// s.pb(x);
	// }
	// cout << count_swaps(s);
	// return 0;
// }

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