#226152 (C++11) No.618 labo-index

• 問題: No.618 labo-index
• ユーザー: yuppe19 😺
• 提出日時: 2017-12-26 00:00:55
• 言語: C++11 (gcc 11.4.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,348 bytes
• コンパイル時間: 346 ms
• コンパイル使用メモリ: 51,328 KB
• 最終ジャッジ日時: 2024-04-27 02:30:40
• 合計ジャッジ時間: 1,449 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

コンパイルメッセージ

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;
}