Submission #426783

#	Time	Username	Problem	Language	Result	Execution time	Memory
426783		Pbezz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	165 ms	18512 KiB

shoes

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

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 1e5+5;
const ll INF = 1e9+7;
ll seg[8*MAXN];

void recalculate(ll node){
seg[node] = seg[2*node+1]+seg[2*node+2];
}

void build(ll node, ll left, ll right){

if(left==right){
seg[node]=0;
}else{
ll middle = (left+right)/2;

build(2*node+1,left,middle);
build(2*node+2,middle+1,right);

recalculate(node);
}
}

void update(ll node, ll left, ll right, ll pos){
//cout<<node<<" "<<left<<" "<<right<<" "<<pos<<endl;
if(left==right){
seg[node]=1;
}else{

ll middle = (left+right)/2;

if(pos<=middle)update(2*node+1,left,middle,pos);
if(pos>=middle+1)update(2*node+2,middle+1,right,pos);

recalculate(node);
}
}

ll querie(ll node, ll left, ll right,ll a, ll b){

if(a<=left&&b>=right){
return seg[node];
}
ll middle = (left+right)/2,res=0;

if(a<=middle)res+=querie(2*node+1,left,middle,a,b);
if(b>=middle+1)res+=querie(2*node+2,middle+1,right,a,b);

return res;
}

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

	ll n = s.size(),i,j,k; n/=2;
	ll match[2*n+2];
	vector<vector<ll>>last(2*n+1);

	for(i=0;i<2*n;i++){
	if(s[i]>0){
	last[s[i]].pb(i);
	}else{
	last[-s[i]+n].pb(i);
	}
}

	for(i=1;i<=n;i++){
	for(k=0;k<(ll)last[i].size();k++){
//	cout<<last[i][k]<<" "<<last[i+n][k]<<"  ";
	match[last[i][k]]=last[i+n][k];
	match[last[i+n][k]]=last[i][k];
	}
}

	build(0,1,2*n);


ll done=0,ans=0;
	for(i=0;i<2*n;i++){//cout<<match[i]<<" ";

	if(match[i]<i)continue;

	done = querie(0,1,2*n,i+1,match[i]+1);

	ans += (match[i]-i-1-done);
//	cout<<i<<" "<<done<<" "<<match[i]-i-1-done<<endl;
	if(s[i]>0)ans++;

	update(0,1,2*n,i+1);//este e opcional
	update(0,1,2*n,match[i]+1);
}

//	for(j=0;j<7;j++)cout<<j<<" "<<seg[j]<<endl;

	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:62:20: warning: unused variable 'j' [-Wunused-variable]
   62 |  ll n = s.size(),i,j,k; n/=2;
      |                    ^

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