Submission #3007594
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 new T()[0]; 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
Submission Time | |
---|---|
Task | B - 特別賞 |
User | cirno3153 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 5096 Byte |
Status | CE |
Compile Error
./Main.cpp: In member function ‘T AVLTree<T>::get(int)’: ./Main.cpp:106:31: error: expected ‘;’ before ‘[’ token if (isEmpty()) return new T()[0]; ^ ./Main.cpp:106:32: error: expected identifier before numeric constant if (isEmpty()) return new T()[0]; ^ ./Main.cpp: In lambda function: ./Main.cpp:106:34: error: expected ‘{’ before ‘;’ token if (isEmpty()) return new T()[0]; ^ ./Main.cpp: In member function ‘T AVLTree<T>::get(int)’: ./Main.cpp:107:2: error: ‘else’ without a previous ‘if’ else if (n < left->count) return left->get(n); ^ ./Main.cpp: In instantiation of ‘T AVLTree<T>::get(int) [with T = std::pair<int, int>]’: ./Main.cpp:203:25: required from here ./Main.cpp:106:30: error: could not convert ‘(operator new(8ul), (<statement>, ((std::pair<int, int>*)<anonymous>)))’ from ‘std::pair<int, int>*’ to ‘std::pair<int, int>’ if (isEmpty()) return new T()[0]; ^