結果

問題 No.618 labo-index
ユーザー sekiya9311sekiya9311
提出日時 2017-12-20 01:15:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 783 ms / 6,000 ms
コード長 4,253 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 186,840 KB
実行使用メモリ 21,628 KB
最終ジャッジ日時 2024-05-09 13:21:43
合計ジャッジ時間 9,940 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,552 KB
testcase_01 AC 5 ms
7,424 KB
testcase_02 AC 5 ms
7,424 KB
testcase_03 AC 5 ms
7,424 KB
testcase_04 AC 6 ms
7,624 KB
testcase_05 AC 7 ms
7,680 KB
testcase_06 AC 5 ms
7,552 KB
testcase_07 AC 5 ms
7,424 KB
testcase_08 AC 5 ms
7,424 KB
testcase_09 AC 6 ms
7,680 KB
testcase_10 AC 6 ms
7,552 KB
testcase_11 AC 6 ms
7,680 KB
testcase_12 AC 6 ms
7,552 KB
testcase_13 AC 6 ms
7,552 KB
testcase_14 AC 6 ms
7,552 KB
testcase_15 AC 6 ms
7,552 KB
testcase_16 AC 7 ms
7,680 KB
testcase_17 AC 5 ms
7,680 KB
testcase_18 AC 8 ms
7,680 KB
testcase_19 AC 242 ms
13,300 KB
testcase_20 AC 312 ms
13,180 KB
testcase_21 AC 255 ms
13,304 KB
testcase_22 AC 279 ms
13,176 KB
testcase_23 AC 282 ms
13,300 KB
testcase_24 AC 254 ms
13,180 KB
testcase_25 AC 294 ms
13,308 KB
testcase_26 AC 286 ms
13,304 KB
testcase_27 AC 284 ms
13,304 KB
testcase_28 AC 233 ms
13,176 KB
testcase_29 AC 270 ms
13,284 KB
testcase_30 AC 250 ms
13,172 KB
testcase_31 AC 272 ms
13,176 KB
testcase_32 AC 295 ms
13,176 KB
testcase_33 AC 265 ms
13,300 KB
testcase_34 AC 683 ms
21,496 KB
testcase_35 AC 783 ms
21,628 KB
testcase_36 AC 220 ms
10,100 KB
testcase_37 AC 488 ms
15,228 KB
testcase_38 AC 5 ms
7,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

// 区間加算，区間参照
// 半開区間!!!
template<typename T = int>
class RangeAddQuery {
private:
     vector<T> data, lazy;
     int sz;
     void push(int k, int l, int r) {
          if (this->lazy[k]) {
               this->data[k] += this->lazy[k] * (r - l);
               if (k * 2 + 2 < sz * 2 - 1) {
                    this->lazy[2 * k + 1] += this->lazy[k];
                    this->lazy[2 * k + 2] += this->lazy[k];
               }
               this->lazy[k] = 0;
          }
     }
     void add(int l, int r, int L, int R, int k, T val) {
           this->push(k, l, r);
          if (L <= l && r <= R) {
               this->lazy[k] += val;
                  this->push(k, l, r);
          } else if (R <= l || r <= L) {
               return;
          } else if (r - l > 1) {
               const int mid = (l + r) / 2;
               this->add(l, mid, L, R, k * 2 + 1, val);
               this->add(mid, r, L, R, k * 2 + 2, val);
                  data[k] = data[k * 2 + 1] + data[k * 2 + 2];
          }
     }
     T query(int l, int r, int L, int R, int k) {
          this->push(k, l, r);
          if (L <= l && r <= R) {
               return data[k];
          } else if (R <= l || r <= L) {
               return 0;
          } else {
               const int mid = (l + r) / 2;
               const T left = this->query(l, mid, L, R, k * 2 + 1);
               const T right = this->query(mid, r, L, R, k * 2 + 2);
               return left + right;
          }
     }
public:
     RangeAddQuery(const int n) {
          this->sz = 1;
          while (this->sz < n) this->sz <<= 1;
          this->data.resize(this->sz * 2 - 1);
          this->lazy.resize(this->sz * 2 - 1);
     }
     void add(int l, int r, T val) {
          this->add(0, this->sz, l, r, 0, val);
     }
     T query(int l, int r) {
          return this->query(0, this->sz, l, r, 0);
     }
};

const int MAX = 1e5 + 10;
int Q;
long long t[MAX], x[MAX], prevX[MAX];
vector<pair<int, long long>> addCntIdx;// addCntIdx[i] = i番目に入ってきたやつのidx, その時点での区間加算値
map<long long, int> comp;
RangeAddQuery<long long> raq(MAX);

int main() {
    scanf("%d", &Q);
    for (int i = 0; i < Q; i++) {
        scanf("%lld%lld", t + i, x + i);
    }

    {
        set<long long> se;
        long long range = 0;
        for (int i = 0; i < Q; i++) {
            if (t[i] == 1) {
                // add
                se.insert(x[i] - range);
                addCntIdx.emplace_back(i, range);
            } else if (t[i] == 2) {
                // erase
            } else {
                // up power
                range += x[i];
            }
        }
        {
            int cnt = 0;
            for (long long e : se) {
                comp[e] = cnt++;
            }
            //comp[*max_element(begin(se), end(se))] = cnt + 1;
        }
    }

    {
        long long range = 0;
        int hCnt = 0;
        for (int i = 0; i < Q; i++) {
            if (t[i] == 1) {
                // add
                const int idx = comp[x[i] - range];
                raq.add(idx, idx + 1, 1);
                hCnt++;
            } else if (t[i] == 2) {
                // erase
                const auto idxAndRageAddVal = addCntIdx[x[i] - 1];
                const int idx = addCntIdx[x[i] - 1].first;
                const long long preRange = addCntIdx[x[i] - 1].second;
                const int cmpIdx = comp[x[idx] - preRange];
                raq.add(cmpIdx, cmpIdx + 1, -1);
                hCnt--;
            } else {
                // up power
                range += x[i];
            }

            long long low = 0, high = hCnt + 1;
            while (high - low > 1) {
                const long long mid = low + (high - low) / 2;
                //cerr << mid << endl;
                auto itr = comp.lower_bound(mid - range);
                long long get = itr == comp.end() ? MAX - 1 : itr->second;
                if (raq.query(get, MAX) >= mid) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            printf("%lld\n", low);
        }
    }

    return 0;
}
0