Submission #847481

#	Time	Username	Problem	Language	Result	Execution time	Memory
847481		Amaarsaa	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	227 ms	277888 KiB

shoes

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

using namespace std;
using ll = long long;
ll mid;
int Sum[1600005];
ll Used[200005] ;
queue < ll > Left[200002], Right[200002];
void Change(ll p, ll lo, ll hi, ll x) {
	if ( lo== hi) {
		Sum[p] = 1;
		return ;
	}
	mid = (lo + hi)/2;
	if ( x <= mid) Change(2 * p, lo, mid, x);
	else Change(2 * p + 1, mid + 1, hi, x);
	Sum[p] = Sum[2 * p] + Sum[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll st, ll fn) {
	if ( st > hi || lo > fn) return 0;
	if ( st <= lo && hi <= fn) {
		return Sum[p];
	}
	mid = (lo + hi)/2;
	return Find(2 * p, lo, mid, st, fn) + Find(2 * p + 1, mid + 1, hi, st, fn);
}


long long count_swaps(vector<int> s) {
	ll n, i, p, m, I, M;
	n = s.size();
	
	for (i = 0; i < s.size(); i ++) {
		if ( s[i] < 0) {
			Left[-s[i]].push(i);
		}
		else Right[s[i]].push(i);
	}	
	long long ans =0;
	for (i = 0; i < s.size(); i ++) {
		if ( Used[i] == 1) continue;
		I = i + Find(1, 0, n-1, i, n - 1);
		p = s[i];
		if ( p < 0) {
			Left[-p].pop();
			m= Right[-p].front();
			Used[m]= 1;
			M = m +  Find(1, 0, n - 1, m, n - 1);
			ans += (M - I - 1);
			Right[-p].pop();
		}
		else {
			Right[p].pop();
			m= Left[p].front();
			Used[m]= 1;
			M = m +  Find(1, 0, n - 1, m, n - 1);
			ans += (M - I );
			Left[p].pop();	
		}
		Change(1, 0, n-1, i);
		Change(1, 0, n-1, m);
		
	}
	return ans;
}
/*
int main () {
	ll X, i, n;
	vector < int > V;
	cin >> n;
	for (i = 0; i < 2 * n; i ++) {
		cin >> X;
		V.push_back(X);
	}
	cout << count_swaps(V) << endl; 
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:34:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (i = 0; i < s.size(); i ++) {
      |              ~~^~~~~~~~~~
shoes.cpp:41:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (i = 0; i < s.size(); i ++) {
      |              ~~^~~~~~~~~~

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