Submission #579945

#	Time	Username	Problem	Language	Result	Execution time	Memory
579945		shezitt	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	154 ms	139328 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
 
const int mxN = 2e5;
long long T[mxN+5];
int n;
 
void add(int i, int x){
	i++;
	while(i <= mxN){
		T[i] += x;
		i += i & -i;
	}
}
 
long long query(int i){
	i++;
	long long sum = 0;
	while(i > 0){
		sum += T[i];
		i -= i & -i;
	}
	return sum;
}
 
long long count_swaps(vector<int> s) {
	n = int(s.size());
	vector<queue<int>> q(mxN+5);
	long long ans = 0;
	for(int i=0; i<n; ++i){
		int aux = 1e5-s[i] ;
		if(!q[aux].empty()){
			int l = q[aux].front();
			q[aux].pop();
			ans += (i-l) - (s[i] > 0) - query(i) + query(l);
			add(l, -1);
		} else {
			q[s[i]+1e5].push(i);
			add(i, 1);
		}
	}
	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