Submission #536518

#	Time	Username	Problem	Language	Result	Execution time	Memory
536518		fuad27	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	240 ms	274480 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'010;
int n;
namespace fenwick {
	long long fen[MAXN];
	void update(int in, int val) {
		in++;
		while(in < MAXN) {
			fen[in]+=val;
			in+=in&(-in);
		}
	}

	long long query(int l) {
		l++;
		long long ans = 0;
		while(l > 0) {
			ans += fen[l];
			l-=l&(-l);
		}
		return ans;
	}
};

long long getNum(long long i) {
	return i + n;
}

long long count_swaps(std::vector<int> v) {
	n = v.size();
	for(int i = 0;i<MAXN;i++) {
		fenwick::fen[i] = 0;
	}
	for(int i = 0;i<MAXN;i++) {
		fenwick::update(i, 1);
	}
	long long ans = 0;
	queue<int> q[2*n+1];
	for(int i = 0;i<n;i++) {
		if(q[getNum(-v[i])].size()!=0) {
			int at = q[getNum(-v[i])].front();
			q[getNum(-v[i])].pop();
			ans+=fenwick::query(i) - fenwick::query(at)-1;
			if(v[i] < 0)ans++;
			fenwick::update(i, -1);
			fenwick::update(at, 1);
		}
		else {
			q[getNum(v[i])].push(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