Submission #1219868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219868		nickolasarapidis	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	392 ms	153840 KiB

shoes

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

const int MAXN = 200005;

vector<long long> cnt(MAXN, 0), ST(4*MAXN, 0);

void update(int v, int l, int r, int k, int x){
	if(l == r){
		ST[v] += x;
		return;
	}
	int m = (l + r)/2;
	if(k <= m){
		update(2*v, l, m, k, x);
	}
	else{
		update(2*v + 1, m + 1, r, k, x);
	}
	ST[v] = ST[2*v] + ST[2*v + 1];
	return;
}

long long sum(int v, int l, int r, int a, int b){
	if(l > b or r < a) return 0;
	if(l >= a and r <= b) return ST[v];
	int m = (l + r)/2;
	return sum(2*v, l, m, a, b) + sum(2*v + 1, m + 1, r, a, b);
}

long long count_swaps(vector<int> S){
	map<int, deque<int>> m;
	int N = S.size();
	long long ans = 0;
	for(int i = 0; i < N; i++){
		if(S[i] > 0 and m[-S[i]].size() > 0){
			int j = m[-S[i]].front();
			ans += i - j - 1 + sum(1, 0, N - 1, j, i);
			update(1, 0, N - 1, i, -1);
			update(1, 0, N - 1, j, 1);
			m[-S[i]].pop_front();
		}
		else if(S[i] < 0 and m[-S[i]].size() > 0){
			int j = m[-S[i]].front();
			ans += i - j + sum(1, 0, N - 1, j, i);
			update(1, 0, N - 1, i, -1);
			update(1, 0, N - 1, j, 1);
			m[-S[i]].pop_front();
		}
		else{
			m[S[i]].push_back(i);
		}
	}
	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