Submission #1075524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075524		mindiyak	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	148 ms	142996 KiB

shoes

#include "shoes.h"
#include <vector>
#include <deque>
#include <iostream>
#define ll long long
#define F first
#define S second
using namespace std;

vector<ll> num_swaps(6e5+8,0);

ll get_swaps(int pos,int l,int r,int ql,int qr){
	if(ql > r || qr<l) return 0;
	if(r<=qr && l>=ql)
		return num_swaps[pos];
	int mid = (l+r)/2;
	return get_swaps(2*pos+1,l,mid,ql,qr) + get_swaps(2*pos+2,mid+1,r,ql,qr);
}
 
void update_swaps(int pos,int l,int r,int index,int val){
	num_swaps[pos] += val;
	if(index == l && l == r){
		return;
	}	
	int mid = (l+r)/2;
	if(index <= mid){
		update_swaps(2*pos+1,l,mid,index,val);
	}else{
		update_swaps(2*pos+2,mid+1,r,index,val);
	}
}


long long count_swaps(std::vector<int> s) {
	ll ans = 0;

	vector<deque<int>> arr(2e5+10);
	int n = s.size();


	for(int i = 0;i<n;i++){
		int left = 0;
		if(s[i] < 0)left = 1;

		// if(left)cerr << "left ";
		// else cerr << "right ";

		// cerr << s[i] << " " << arr[-s[i]+1e5].size() << " ";
		if(arr[-s[i]+1e5].size() > 0){
			int a = arr[-s[i]+1e5][0];
			arr[-s[i]+1e5].pop_front();
			// cerr << a.F << " " << a.S << " " << cnt << endl;
			// cout << ans << endl;

			ans += i - a - get_swaps(0,0,n-1,a,i);
			update_swaps(0,0,n-1,i,1);
			update_swaps(0,0,n-1,a,-1);
			if(left == 0)ans -= 1;

		}else{
			// cerr << s[i]+1e5 << " " << i << " " << cnt << endl;
			arr[s[i]+1e5].push_back(i);
		}
	}

	
	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