Submission #292482

#	Time	Username	Problem	Language	Result	Execution time	Memory
292482		miss_robot	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	348 ms	275124 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

#pragma GCC optimize("O3")

using namespace std;

const int N = 2e5+1, L = 262144;
int n;
int done[N], t[2*L];
deque<int> l[N], r[N];

int qry(int a){
	a += L;
	int r = 0;
	while(a) r += t[a], a >>= 1;
	return r;
}

void upd(int a, int b, int l, int r, int k){
	if(l > b || r < a) return;
	if(a <= l && r <= b){
		t[k]++;
		return;
	}
	upd(a, b, l, (l+r)>>1, k<<1), upd(a, b, ((l+r)>>1)+1, r, (k<<1)|1);
}

long long count_swaps(vector<int> s){
	n = s.size();
	long long sol = 0;
	for(int i = 0; i < n; i++){
		if(s[i] < 0) l[-s[i]].push_back(i);
		else r[s[i]].push_back(i);
	}
	for(int i = 0; i < n; i++){
		if(done[i]) continue;
		int a = i + qry(i), t, b;
		if(s[i] < 0){
			t = r[-s[i]].front();
			b = t + qry(t);
			r[-s[i]].pop_front();
			l[-s[i]].pop_front();
		}
		else{
			t = l[s[i]].front();
			b = t + qry(t);
			l[s[i]].pop_front();
			r[s[i]].pop_front();
		}
		sol += b-a;
		if(s[i] < 0) sol--;
		upd(i, t, 0, L-1, 1);
		done[i] = done[t] = 1;
	}
	return sol;
}

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