Submission #498291

#	Time	Username	Problem	Language	Result	Execution time	Memory
498291		inluminas	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	83 ms	21236 KiB

shoes

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=2e5+10;
int a[lmt],tree[lmt];
vector<int>pos[lmt][2];

void updet(int idx,int n){
	while(idx<=n){
		tree[idx]++;
		idx+=(idx&-idx);
	}
	return;
}

int read(int idx){
	int sum=0;
	while(idx>0){
		sum+=tree[idx];
		idx-=(idx&-idx);
	}
	return sum;
}

int query(int l,int r){
	if(l>r) return 0;
	return read(r)-read(l-1);
}

ll count_swaps(std::vector<int> b) {
	
	int n=b.size();
	for(int i=0;i<n;i++) a[i+1]=b[i];

	for(int i=1;i<=n;i++){
		bool on=1;
		if(a[i]<0) on=0;
		pos[abs(a[i])][on].push_back(i);
	}

	ll ans=0;
	vector<pair<int,int>>v;

	for(int i=1;i<=n;i++){
		for(int j=0;j<2;j++){
			sort(pos[i][j].begin(),pos[i][j].end(),[](int x,int y){
				return x>y;
			});
		}
		while(!pos[i][0].empty()){
			int l=pos[i][0].back(),r=pos[i][1].back();
			if(l>r){
				ans++;
				swap(l,r);
			}
			v.push_back({l,r});
			for(int j=0;j<2;j++) pos[i][j].pop_back();
		}
	}

	sort(v.begin(),v.end());

	for(auto [x,y]:v){
		ans+=query(x,n);
		ans+=query(y,n);
		updet(x,n);
		updet(y,n);
	}

	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