Submission #1227957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227957		walizamanee	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	257 ms	277024 KiB

shoes

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


int one , two , n;
deque<int> bam[200001] , dan[200001] , a;
long long ans , st[800001] , ek , dui;

void build( int node , int l , int r ) {
	 if( l == r ) st[node] = 1;
	 else{
		int m = ( l + r ) / 2;
		build( node * 2 , l , m );
		build( (node * 2) + 1 , m + 1 , r );
		st[node] = st[node * 2] + st[(node * 2) + 1];
	 }
}

void update( int node , int l , int r , int here ) {
	if( l == r ) st[node] = 0;
	else{
		int m = (l + r ) / 2;
		if( here <= m ) update( node * 2 , l , m , here );
		else update( (node * 2 ) + 1 , m + 1 , r , here );
		st[node] = st[node * 2] + st[(node * 2) + 1];
	}
}

void getans( int node , int l , int r , int uno , int dos ) {
	if( l >= uno && r <= dos ) ans += st[node];
	else{
		int m = (l + r ) / 2;
		if( uno <= m ) getans( node * 2 , l , m , uno , dos );
		if( dos > m ) getans( (node * 2) + 1 , m + 1 , r , uno , dos );
	}
}

long long count_swaps(vector<int> s) {
	ans = 0;
	n = (int)s.size();
	a.clear();
	for( int z = 0; z <= n; z++ ) {
		bam[z].clear();
		dan[z].clear();
	}
	for( int z = 0; z < n; z++ ) a.push_back(s[z]);
    for( int z = 0; z < n; z++ ) {
		if( a[z] < 0 ) {
			bam[(a[z] * (-1))].push_back(z);
		}
		else dan[a[z]].push_back(z);
	}
	build( 1 , 0 , n - 1 );
	for( int z = 0; z < n; z++ ) {
		if( a[z] != 0 ) {
			if( a[z] > 0 ) ans++;
			one = bam[abs(a[z])].front();
			two = dan[abs(a[z])].front();
			bam[abs(a[z])].pop_front();
			dan[abs(a[z])].pop_front();
			if( one > two ) swap(one , two);
			update( 1 , 0 , n - 1 , one );
			update( 1 , 0 , n - 1 , two );
			a[one] = 0;
			a[two] = 0;
			getans( 1 , 0 , n - 1 , one , two );

		}
	}
	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