Submission #1025284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025284		HD1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	206 ms	275972 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) ll(x.size())
using namespace std;
typedef long long ll;
typedef pair<ll,ll>ii;
const ll MAX=2e5+10;
const ll INF=1e18;
ll n;
bool esta[MAX];
ll bit[MAX];
struct andre{
	deque<ll> der;
	deque<ll> iz;
	andre(){}
	void add(ll x, ll i){
		if(i<0)  iz.push_back(x); 
		else    der.push_back(x);
	}
	void quitar(ll x){
		if(x==0) iz.pop_front();
		else    der.pop_front();
	}
	ll val(ll x){
		if(x==0)return *iz.begin();
		else return *der.begin();
	}
};//0 iz 1 der
andre A[MAX];
void update(ll i, ll x){
	while(i<=n){
		bit[i]+=x;
		i+=i&(-i);
	}
	return;
}
ll query(ll i){
	ll ans=0;
	while(i){
		ans+=bit[i];
		i-=i&(-i);
	}
	return ans;
}
long long count_swaps(std::vector<int> s) {
	n=sz(s);
	//cout<<n<<'\n';
	//cout<<"avocado"<<'\n';
	ll ans=0;
	for(ll i=0; i<n; i++){
		esta[i+1]=true;
		A[abs(s[i])].add(i+1, s[i]);
		//cout<<"avocado"<<'\n';
		update(i+1, 1);
	}
	for(int i=0; i<n; i++){
		//cout<<"avocado"<<'\n';
		ll aux=abs(s[i]);
		ll l=0, r=0;
		//cout<<"avocado"<<'\n';
		if(s[i]<0 && esta[i+1]){//es izquierda
			//cout<<"avocado"<<'\n';
			l=A[aux].val(0);
			r=A[aux].val(1);
			A[aux].quitar(0);
			A[aux].quitar(1);
			ans+=query(r-1)-query(l);
			//cout<<"avocado"<<'\n';
		}
		else if(esta[i+1]){
			//cout<<"avocado"<<'\n';
			l=A[aux].val(1);
			r=A[aux].val(0);
			A[aux].quitar(1);
			A[aux].quitar(0);
			ans+=query(r-1)-query(l-1);
			//cout<<l <<" "<<r<<'\n';
			//cout<<query(r-1)-query(l-1)<<'\n';
		}
		if(esta[i+1]){
			esta[l]=false;
			esta[r]=false;
			update(l,-1);
			update(r,-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