結果
問題 | No.618 labo-index |
ユーザー | yuppe19 😺 |
提出日時 | 2017-12-26 00:00:55 |
言語 | C++11 (gcc 11.4.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,348 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 51,600 KB |
最終ジャッジ日時 | 2024-11-14 20:18:12 |
合計ジャッジ時間 | 1,960 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:144:3: error: ‘vector’ was not declared in this scope 144 | vector<i64> memo; | ^~~~~~ main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’? 2 | #include <algorithm> +++ |+#include <vector> 3 | using namespace std; main.cpp:144:13: error: expected primary-expression before ‘>’ token 144 | vector<i64> memo; | ^ main.cpp:144:15: error: ‘memo’ was not declared in this scope 144 | vector<i64> memo; | ^~~~ main.cpp:141:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 141 | int Q; scanf("%d", &Q); | ~~~~~^~~~~~~~~~ main.cpp:147:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 147 | scanf("%d%lld", &t, &x); | ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <algorithm> using namespace std; using i64 = long long; using u32 = unsigned int; u32 uy = time(NULL); u32 xorshift32() { uy ^= uy << 14; uy ^= uy >> 13; uy ^= uy << 15; return uy; } // RBST (Randomised Binary Search Tree) template <class T> struct RBST { struct Node { // {{{ Node constexpr static T nullval = -1; // valueAt() で不正な場所が指定されたときに返す値. T val; int treeSize; Node *lo, *hi; Node(T val) : val(val), treeSize(1), lo(nullptr), hi(nullptr) {} int size() { if(this == nullptr) { return 0; } return treeSize; } Node* update() { treeSize = lo->size() + hi->size() + 1; return this; } static Node* merge(Node *l, Node *r) { if(l == nullptr) { return r; } if(r == nullptr) { return l; } int lSize = l->size(), rSize = r->size(); if(xorshift32() % (lSize + rSize) < lSize) { l->hi = merge(l->hi, r); return l->update(); } else { r->lo = merge(l, r->lo); return r->update(); } } pair<Node*, Node*> split(int k) { // [0, k), [k, n) if(this == nullptr) { return make_pair(nullptr, nullptr); } if(k <= lo->size()) { auto s = lo->split(k); lo = s.second; return make_pair(s.first, update()); } else { auto s = hi->split(k - lo->size() - 1); hi = s.first; return make_pair(update(), s.second); } } int indexOf(T val) { if(this == nullptr) { return -1; } if(val == this->val) { return lo->size(); } if(val < this->val) { return lo->indexOf(val); } else { return lo->size() + 1 + hi->indexOf(val); } } T valueAt(int pos) { if(this == nullptr) { return nullval; } int loSize = lo->size(); if(loSize == pos) { return val; } if(loSize > pos) { return lo->valueAt(pos); } else { return hi->valueAt(pos - lo->size() - 1); } } int lowerBound(T val) { if(this == nullptr) { return 0; } if(val <= this->val) { return lo->lowerBound(val); } return hi->lowerBound(val) + lo->size() + 1; } int upperBound(T val) { if(this == nullptr) { return 0; } if(val >= this->val) { return lo->size() + 1 + hi->upperBound(val); } return lo->upperBound(val); } int count(T val) { return upperBound(val) - lowerBound(val); } Node* insert(int pos, T val) { Node *p = new Node(val); auto s = split(pos); return merge(merge(s.first, p), s.second); } Node* insert(T val) { return insert(lowerBound(val), val); } Node* deleteAt(int pos) { auto s = split(pos); auto t = s.second->split(1); t.first = nullptr; return merge(s.first, t.second); } void dump(int x) { if(this == nullptr) { return; } fprintf(stderr, "%c", "([{"[x%3]); lo->dump(x+1); fprintf(stderr, "%d", val); hi->dump(x+1); fprintf(stderr, "%c", ")]}"[x%3]); } }; // }}} Node *root; RBST() { root = nullptr; } int size() { return root->size(); } int indexOf(T val) { return root->indexOf(val); } T valueAt(int pos) { return root->valueAt(pos); } int lowerBound(T val) { return root->lowerBound(val); } int upperBound(T val) { return root->upperBound(val); } int count(T val) { return root->count(val); } void insert(T val) { root = root->insert(val); } void deleteAt(int pos) { root = root->deleteAt(pos); } void deleteValue(T val) { deleteAt(indexOf(val)); } void dump() { root->dump(0); fprintf(stderr, "\n"); } }; int main(void) { int Q; scanf("%d", &Q); i64 border = 0; RBST<i64> tree; vector<i64> memo; int t; i64 x; for(int i=0; i<Q; ++i) { scanf("%d%lld", &t, &x); if(t == 1) { memo.push_back(x + border); tree.insert(memo.back()); } else if(t == 2) { tree.deleteValue(memo[--x]); } else { border -= x; } i64 lo = -Q, hi = Q; while(hi - lo > 1) { i64 md = (lo + hi) / 2; i64 val = md + border; if(tree.size() - tree.lowerBound(val) >= md) { // 値が val 以上の要素数を数える lo = md; } else { hi = md; } } printf("%lld\n", lo); } return 0; }