Submission #757119

#	Time	Username	Problem	Language	Result	Execution time	Memory
757119		Piokemon	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	150 ms	15856 KiB

shoes

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

constexpr int N=1e5;
constexpr int base=(1<<18);
vector<int> gdzie[2*N+9];
int tree[2*base+9];
bool used[2*N+9];

void add(int x, int a, int b, int p, int k, int val){
	if (a>k || b<p) return;
	if (p<=a && b<=k){
		tree[x] += val;
		return;
	}
	int mid = (a+b)/2;
	add(2*x,a,mid,p,k,val);
	add(2*x+1,mid+1,b,p,k,val);
}

ll query(int x){
	x += base;
	int odp=0;
	while(x>0){
		odp += tree[x];
		x = x>>1;
	}
	return odp;
}

ll count_swaps(vector<int> s) {
	ll odp = 0,n=s.size()/2;
	for (int x=2*n-1;x>=0;x--){
		gdzie[s[x]+n].push_back(x);
		add(1,0,base-1,x,x,x); 
	}
	for (int x=0;x<2*n;x++){
		if (used[x]) continue;
		odp += query(gdzie[-s[x]+n].back());
		used[x] = 1; used[gdzie[-s[x]+n].back()] = 1;
		if (s[x]<0)odp--;
		add(1,0,base-1,x,2*n-1,-1);
		add(1,0,base-1,gdzie[-s[x]+n].back(),2*n-1,-1);
		gdzie[s[x]+n].pop_back();
		gdzie[-s[x]+n].pop_back();
	}
	return odp;
}

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