Submission #1184087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184087		xnqs	medians (balkan11_medians)	C++20	5 / 100	8 ms	1860 KiB

medians

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

template<typename Type>
class FenwickTree {
private:
	std::vector<Type> bit;
public:
	FenwickTree(int n = 0, Type v = 0) {
		Assign(n, v);
	}

	void Assign(int n = 0, int v = 0) {
		bit.assign(n+1, 0);
		for (int i = 1; i <= n; i++) {
			bit[i] += v;
			if (i+(i&-i)<=n) {
				bit[i+(i&-i)] += bit[i];
			}
		}
	}

	void Add(int pos, Type val) {
		while (pos < bit.size()) {
			bit[pos] += val;
			pos += pos&-pos;
		}
	}

	Type Query(int pos) {
		Type ret = 0;
		while (pos > 0) {
			ret += bit[pos];
			pos ^= pos&-pos;
		}
		return ret;
	}

	Type Query(int l, int r) {
		return Query(r) - Query(l-1);
	}

	int BinaryLifting(Type val) {
		int ret = 0;
		for (int step = 1<<18; step; step >>= 1) {
			if (ret+step < bit.size() && val - bit[ret+step] > 0) {
				val -= bit[ret+step];
				ret += step;
			}
		}
		return ret+1;
	}
};

int x;
int arr[100005];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x;
	FenwickTree<int> fnwk_remaining(2*x-1, 1);
	FenwickTree<int> fnwk_deleted(2*x-1, 0);
	for (int i = 1, tmp; i <= x; i++) {
		std::cin >> tmp;

		//std::cout << tmp << " " << fnwk.Query(tmp-1) << " " << fnwk.Query(tmp+1, 2*x-1) << "\n";

#if 1
		if (i==1) {
			std::cout << tmp << " ";
			fnwk_remaining.Add(tmp, -1);
			fnwk_deleted.Add(tmp, 1);
			continue;
		}

		int less = fnwk_deleted.Query(tmp-1);
		int greater = fnwk_deleted.Query(tmp+1, 2*x-1);

		if (less == greater) {
			int a = fnwk_remaining.BinaryLifting(1);
			int b = fnwk_remaining.BinaryLifting(fnwk_remaining.Query(1,2*x-1));

			std::cout << a << " " << b << " ";

			fnwk_remaining.Add(a, -1);
			fnwk_remaining.Add(b, -1);
			fnwk_deleted.Add(a, 1);
			fnwk_deleted.Add(b, 1);
		}
		else if (less == greater-1) {
			int a = fnwk_remaining.BinaryLifting(1);
			int b = tmp;

			std::cout << a << " " << b << " ";

			fnwk_remaining.Add(a, -1);
			fnwk_remaining.Add(b, -1);
			fnwk_deleted.Add(a, 1);
			fnwk_deleted.Add(b, 1);
		}
		else if (less == greater+1) {
			int a = tmp;
			int b = fnwk_remaining.BinaryLifting(fnwk_remaining.Query(1,2*x-1));

			std::cout << a << " " << b << " ";

			fnwk_remaining.Add(a, -1);
			fnwk_remaining.Add(b, -1);
			fnwk_deleted.Add(a, 1);
			fnwk_deleted.Add(b, 1);
		}
#endif
	}

	std::cout << "\n";
}

• Subtask 1: 5 / 65
• Subtask 2: 0 / 35