Submission #1266143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266143		WH8	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	91 ms	26952 KiB

shoes

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

int fw[200005];
int qry(int x){
	int ret=0;
	while(x){
		ret+=fw[x];
		x-=(x&(-x));
	}
	return ret;
}
void upd(int x, int v){
	while(x <= 200005){
		fw[x]+=v;
		x+=(x&(-x));
	}
}

long long count_swaps(vector<int> s) {
	int n=s.size();
	vector<vector<vector<int>>> szs(n+1, vector<vector<int>>(2));
	for(int i=0;i<n;i++){
		if(s[i] < 0){
			szs[-s[i]][0].push_back(i);
		}
		else {
			szs[s[i]][1].push_back(i);
		}
	}
	vector<int> rgt(n, -1);
	long long ans=0;
	for(int i=1;i<=n;i++){
		assert(szs[i][0].size() == szs[i][1].size());
		for(int j=0;j<(int)szs[i][0].size();j++){
			if(szs[i][1][j] < szs[i][0][j]){
				ans++;
			}
			rgt[min(szs[i][1][j], szs[i][0][j])]=max(szs[i][1][j], szs[i][0][j]);
		}
	}
	//~ cout<<ans<<endl;
	for(int i=0;i<n;i++){
		if(rgt[i]==-1)continue;
		int l=i+qry(i), r=rgt[i]+qry(rgt[i]);
		//~ printf("i %lld, l %lld, r %lld\n", i, l, r);
		assert(l < r);
		ans += r-l-1;
		
		upd(i+1, 1);
		upd(rgt[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