Submission #406053

#	Time	Username	Problem	Language	Result	Execution time	Memory
406053		ngrace	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	576 ms	28228 KiB

shoes

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

vector<int> st(2*4*100000 + 5,0);

int n;

void update(int cur, int l, int r, int tar){
	if(l==r){
		st[cur]=1;
	}
	else{
		int m=(l+r)/2;
		if(tar<=m){
			update(cur*2,l,m,tar);
		}
		else{
			update(cur*2+1,m+1,r,tar);
		}
		st[cur]=st[cur*2]+st[cur*2+1];
	}
}

int query(int cur, int l, int r, int ql, int qr){
	if(ql>qr){
		return 0;
	}
	if(ql<=l && r<=qr){
		return st[cur];
	}
	int m=(l+r)/2;
	return query(cur*2,l,m,ql,min(m,qr)) + query(cur*2+1,m+1,r,max(m+1,ql),qr);
}

void update(int tar){//updates point to 1
	update(1,1,2*n,tar+1);
}

int query(int ql, int qr){
	return query(1,1,2*n,ql+1,qr+1);
}

long long count_swaps(vector<int> s) {
	n=s.size()/2;
	long long out=0;

	map<int,priority_queue<int>> next;
	for(int i=0;i<2*n;i++){
		next[s[i]].push(-i);
	}
	//maps a size to the next -ve index of that size

	for(int i=0;i<2*n;i++){
		if(query(i,i)==1){
			continue;
		}
		if(s[i]>0){
			out++;//final swap if wrong way around
		}
		int ind=-next[-s[i]].top();
		next[-s[i]].pop();
		next[s[i]].pop();
		out+=ind-i-1;
		out-=query(i,ind);
		update(i);
		update(ind);
	}

	return out;
}

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