Submission #1206019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206019		JakobZorz	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	202 ms	25504 KiB

shoes

#include "shoes.h"
#include<map>
using namespace std;
typedef long long ll;

const int TREE_SIZE=1<<18;
int tree[2*TREE_SIZE];

void upd(int i,int x){
	i+=TREE_SIZE;
	tree[i]=x;
	while(i!=1){
		i/=2;
		tree[i]=tree[2*i]+tree[2*i+1];
	}
}

int get(int node,int rl,int rr,int l,int r){
	if(r<=rl||rr<=l)
		return 0;
	if(l<=rl&&rr<=r)
		return tree[node];
	int m=(rl+rr)/2;
	int r1=get(2*node,rl,m,l,r);
	int r2=get(2*node+1,m,rr,l,r);
	return r1+r2;
}

int get(int l,int r){
	return get(1,0,TREE_SIZE,l,r);
}

ll count_swaps(vector<int>arr){
	int n=(int)arr.size();
	vector<bool>alive(n,true);
	for(int i=0;i<n;i++)
		upd(i,1);
	map<int,vector<int>>mp;
	for(int i=n-1;i>=0;i--)
		mp[arr[i]].push_back(i);
	ll res=0;
	for(int i=0;i<n;i++){
		if(!alive[i])
			continue;
		int v=arr[i];
		if(v>0)
			res++;
		/*for(int j=i+1;j<n;j++)
			if(alive[j]&&arr[j]==-v){
				i2=j;
				break;
			}*/
		while(!alive[mp[-v].back()])
			mp[-v].pop_back();
		int i2=mp[-v].back();
		alive[i2]=false;
		upd(i2,0);
		alive[i]=false;
		upd(i,0);
		/*for(int j=i;j<i2;j++)
			res+=alive[j];*/
		res+=get(i,i2);
	}
	return res;
}


// 1 1 -1 -1

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