Submission #589426

#	Time	Username	Problem	Language	Result	Execution time	Memory
589426		farhan132	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	77 ms	20732 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 2e5 + 5;

struct fenwick{
  ll ft[N];
  void build(){
  	memset(ft, 0 ,sizeof(ft));
  	return;
  }
  void up(ll p, ll x) {
    for(; p < N; p += p & -p)
      ft[p] += x;
  } 
  ll sum(ll l, ll r) {
  	if(r < l) return 0;
    ll ret = 0;
    for(--l; l > 0; l -= l & -l) ret -= ft[l];
    for(; r > 0; r -= r & -r) ret += ft[r];
    return ret;
  }
};

ll a[N];
vector < ll > v0[N], v1[N];

long long count_swaps(std::vector<int> s) {

	ll n = s.size() / 2;

	fenwick T; T.build();

	for(ll i = 1; i <= 2*n; i++){
		a[i] = s[i - 1];
		T.up(i, 1);
		if(a[i] < 0) v0[-a[i]].pb(i);
		else v1[a[i]].pb(i);
	}
	for(ll i = n; i >= 1; i--){
		reverse(v1[i].begin(), v1[i].end());
		reverse(v0[i].begin(), v0[i].end());
	}
	ll ans = 0;
	for(ll i = 1; i <= 2*n; i++){
		if(T.sum(i, i) == 0) continue;
		ll S = abs(a[i]);
		ll st[2] = {v0[S].back(), v1[S].back()};
		T.up(st[0], -1);
		T.up(st[1], -1);
		ans += T.sum(i, st[0]) + T.sum(i, st[1]) + (st[1] < st[0]);
		v0[S].pop_back();
		v1[S].pop_back();
	}

	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