Submission #298983

#	Time	Username	Problem	Language	Result	Execution time	Memory
298983		TMJN	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	131 ms	15736 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;


int N,tree[1<<19];
vector<int>vl[100001],vr[100001];

void add(int l,int r){
	l+=(1<<18);
	r+=(1<<18);
	while(l<r){
		if(l&1)tree[l]++;
		if(~r&1)tree[r]++;
		l=(l+1)/2;
		r=(r-1)/2;
	}
	if(l==r)tree[l]++;
}

int calc(int x){
	int a=0;
	x+=(1<<18);
	while(x){
		a+=tree[x];
		x/=2;
	}
	return a;
}


long long count_swaps(vector<int>v) {
	N=v.size();
	long long res=0;
	for(int i=N-1;i>=0;i--){
		if(v[i]<0){
			vl[-v[i]].push_back(i);
		}
		else{
			vr[v[i]].push_back(i);
		}
	}
	for(int i=0;i<N;i++){
		if(v[i]<0){
			if(vl[-v[i]].empty()||vl[-v[i]].back()!=i)continue;
			vl[-v[i]].pop_back();
			res+=vr[-v[i]].back()-i-1;
			res-=calc(i)-calc(vr[-v[i]].back());
			add(i,vr[-v[i]].back());
			vr[-v[i]].pop_back();
		}
		else{
			if(vr[v[i]].empty()||vr[v[i]].back()!=i)continue;
			vr[v[i]].pop_back();
			res+=vl[v[i]].back()-i;
			res-=calc(i)-calc(vl[v[i]].back());
			add(i,vl[v[i]].back());
			vl[v[i]].pop_back();
		}
	}
	return res;
}

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