結果
| 問題 | No.618 labo-index |
| ユーザー |
 yuppe19 😺
|
| 提出日時 | 2017-12-26 00:00:55 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.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 { // {{{ Nodeconstexpr 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;}