Submission #3007603

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;

template <typename T> class AVLTree {
	private:
		bool hasValue;
		AVLTree *left;
		AVLTree *right;
		T value;
		int height;
		int count;
		void cng(AVLTree<T> *t);
		void calc();
		void rotateLeft();
		void rotateRight();
		void rotate();
	public:
		AVLTree();
		void set(T n);
		bool search(T n);
		T get(int n);
		T getMin();
		T getMax();
		int getSmaller(T n);
		int getGreater(T n);
		int getSize();
		bool remove(T n);
		bool removeMin();
		bool removeMax();
		void clear();
		bool isEmpty();
		void getList(vector<T> &l);
};

template <typename T> AVLTree<T>::AVLTree() {
	clear();
}

template <typename T> void AVLTree<T>::calc() {
	if (isEmpty()) return;
	height = max(left->height, right->height) + 1;
	count = left->count + right->count + 1;
}

template <typename T> void AVLTree<T>::cng(AVLTree<T> *t) {
	swap(left, t->left);
	swap(right, t->right);
	swap(value, t->value);
}

template <typename T> void AVLTree<T>::rotateLeft() {
	AVLTree *tmp = right, *tmp2 = right->left;
	cng(right);
	left = tmp;
	left->right = tmp2;
	left->calc();
	calc();
}

template <typename T> void AVLTree<T>::rotateRight() {
	AVLTree *tmp = left, *tmp2 = left->right;
	cng(left);
	right = tmp;
	right->left = tmp2;
	right->calc();
	calc();
}

template <typename T> void AVLTree<T>::rotate() {
	if (isEmpty()) return;
	if (left->height > right->height + 1) {
		if (left->left->height < left->right->height) left->rotateLeft();
		rotateRight();
	} else if (left->height + 1 < right->height) {
		if (right->left->height > right->right->height) right->rotateRight();
		rotateLeft();
	}
	calc();
}

template <typename T> void AVLTree<T>::set(T n) {
	if (isEmpty()) {
		hasValue = true;
		value = n;
		left = new AVLTree<T>;
		right = new AVLTree<T>;
	} else if (n < value) {
		left->set(n);
	} else {
		right->set(n);
	}
	rotate();
}

template <typename T> bool AVLTree<T>::search(T n) {
	if (!hasValue) return false;
	else if (value == n) return true;
	else if (value < n) return left->search(n);
	else return right->search(n);
}

template <typename T> T AVLTree<T>::get(int n) {
	if (isEmpty()) return value;
	else if (n < left->count) return left->get(n);
	else if (n == left->count) return value;
	else return right->get(n - left->count - 1);
}

template <typename T> T AVLTree<T>::getMin() {
	return left->hasValue ? left->getMin() : value;
}

template <typename T> T AVLTree<T>::getMax() {
	return right->hasValue ? right->getMax() : value;
}

template <typename T> int AVLTree<T>::getSmaller(T n) {
	if (isEmpty()) return 0;
	else if (n < value) return left->getSmaller(n);
	return left->count + 1 + right->getSmaller(n);
}

template <typename T> int AVLTree<T>::getGreater(T n) {
	if (isEmpty()) return 0;
	else if (n > value) return right->getGreater(n);
	return left->getGreater(n) + 1 + right->count;
}

template <typename T> int AVLTree<T>::getSize() {
	return count;
}

template <typename T> bool AVLTree<T>::remove(T n) {
	if (isEmpty()) return false;
	if (n < value) return left->remove(n);
	else if (n > value) return right->remove(n);
	else {
		right->remove(n);
		left->remove(n);
		if (left->hasValue) {
			value = left->getMax();
			if (!left->removeMax()) left = left->left;
		} else if (right->hasValue) {
			value = right->getMin();
			if (!right->removeMin()) right = right->right;
		} else clear();
	}
	rotate();
	return true;
}

template <typename T> bool AVLTree<T>::removeMin() {
	if (isEmpty() || !left->hasValue) return false;
	if (!left->left->hasValue) {
		left = left->right;
		return true;
	}
	return left->removeMin();
}

template <typename T> bool AVLTree<T>::removeMax() {
	if (isEmpty() || !right->hasValue) return false;
	if (!right->right->hasValue) {
		right = right->left;
		return true;
	}
	return right->removeMax();
}

template <typename T> void AVLTree<T>::clear() {
	hasValue = false;
	height = 0;
	count = 0;
	left = NULL;
	right = NULL;
}

template <typename T> bool AVLTree<T>::isEmpty() {
	return !hasValue;
}

template <typename T> void AVLTree<T>::getList(vector<T> &l) {
	if (isEmpty()) return;
	left->getList(l);
	l.push_back(value);
	right->getList(l);
}

const int MAX = 100000;

int main() {
	int N, K, X;
	cin >> N >> K;
	AVLTree<pair<int, int> > tree;
	for (int i = 0;i < K;i ++) {
		cin >> X;
		tree.set(make_pair(X, i + 1));
	}
	for (int i = K;i < N;i ++) {
		cout << tree.get(K - 1).second << endl;
		cin >> X;
		tree.set(make_pair(X, i + 1));
	}
	cout << tree.get(K - 1).second << endl;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

面倒になったので平衡二分探索木で殴ります
*/

Submission Info

Judge Result