Submission #486847

#	Time	Username	Problem	Language	Result	Execution time	Memory
486847		TypeYippie	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	353 ms	284184 KiB

shoes

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

int tree[1000005];

int getLeft(int x){
	return 2*x+1;
}

int getRight(int x){
	return 2*x+2;
}

void update(int target, int il, int ir, int idx, int val){
	if(il > ir || ir < target || il > target) return;
	if(il == ir){
		tree[idx] += val;
		return;
	}
	int mid = il+(ir-il)/2;
	update(target, il, mid, getLeft(idx), val);
	update(target, mid+1, ir, getRight(idx), val);
	tree[idx] = tree[getLeft(idx)]+tree[getRight(idx)];
}

int getVal(int left, int right, int il, int ir, int idx){
	if(il > ir || ir < left || il > right) return 0;
	if(il >= left && ir <= right){
		return tree[idx];
	}
	int mid = il+(ir-il)/2;
	return getVal(left, right, il, mid, getLeft(idx)) + getVal(left, right, mid+1, ir, getRight(idx));
}

long long count_swaps(vector<int> s) {
	for(int i = 0; i < 1000005; i++) tree[i] = 0;
	int n = s.size();
	for(int i = 0; i < n; i++){
		update(i, 0, n-1, 0, 1);
	}
	vector<vector<queue<int>>> prev(n+1, vector<queue<int>>(2));
	int pos[n];
	for(int i = 0; i < n; i++){
		if(s[i] < 0){
			if(!prev[-s[i]][0].empty()){
				pos[prev[-s[i]][0].front()] = i;
				pos[i] = -1;
				prev[-s[i]][0].pop();
			} else {
				prev[-s[i]][1].push(i);
			}
		} else {
			if(!prev[s[i]][1].empty()){ 
				pos[prev[s[i]][1].front()] = i;
				pos[i] = -1;
				prev[s[i]][1].pop();
			} else {
				prev[s[i]][0].push(i);
			}
		}
	}
	long long ans = 0;
	for(int i = 0; i < n; i++){
		if(pos[i] == -1) continue;
		if(s[i] < 0){
			ans += getVal(i+1, pos[i]-1, 0, n-1, 0);
			update(pos[i], 0, n-1, 0, -1);
		} else {
			ans += getVal(i+1, pos[i]-1, 0, n-1, 0)+1;
			update(pos[i], 0, n-1, 0, -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