結果

問題 No.618 labo-index
コンテスト
ユーザー 0w1
提出日時 2018-05-09 22:17:42
言語 JavaScript
(node v25.2.1)
結果
WA  
実行時間 -
コード長 2,341 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 77 ms
コンパイル使用メモリ 5,248 KB
実行使用メモリ 88,376 KB
最終ジャッジ日時 2024-10-13 00:41:04
合計ジャッジ時間 32,721 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Sgt {

  constructor(size) {
    this.sum = new Array(size << 2).fill(0);
  }

  add(t, lb, rb, k, v) {
    rb = rb || this.sum.length >> 2;
    if (rb - lb == 1) {
      this.sum[t] += v;
      return;
    }
    let mb = lb + rb >> 1;
    if (k < mb) this.add(t << 1, lb, mb, k, v);
    else this.add(t << 1 | 1, mb, rb, k, v);
    this.sum[t] = this.sum[t << 1] + this.sum[t << 1 | 1];
  }

  qry(t, lb, rb, ql, qr) {
    rb = rb || this.sum.length >> 2;
    qr = qr || rb;
    if (qr <= lb || rb <= ql) return 0;
    if (ql <= lb && rb <= qr) return this.sum[t];
    let mb = lb + rb >> 1;
    return this.qry(t << 1, lb, mb, ql, qr) + this.qry(t << 1 | 1, mb, rb, ql, qr);
  }

}

function Main(input) {

  let inputs = input.split('\n');

  let q = Number(inputs[0]);
  let ts = [...Array(q).keys()].map((e) => inputs[1 + e].split(' ').map((x) => x - 0));

  let ps = new Array(q);
  let qid = new Array(0);
  let sadd = 0;
  for (let i = 0; i < q; ++i) {
    if (ts[i][0] == 1) {
      ps[i] = ts[i][1] - sadd;
      qid.push(i);
    } else if (ts[i][0] == 3) {
      sadd += ts[i][1];
    }
  }

  let sorted_ps = ps.slice(0).filter((e) => e != null).sort();
  let uniq_ps = new Array(0);
  let psmp = {};
  for (let i = 0, j = 0; i < sorted_ps.length; ++i) {
    if (i == 0 || sorted_ps[i] != sorted_ps[i - 1]) {
      psmp[sorted_ps[i]] = uniq_ps.length;
      uniq_ps.push(sorted_ps[i]);
    }
  }

  let root = new Sgt(uniq_ps.length);
  let gadd = 0;
  for (let i = 0; i < q; ++i) {
    if (ts[i][0] == 1) {
      root.add(1, 0, null, psmp[ps[i]], 1);
    } else if (ts[i][0] == 2) {
      root.add(1, 0, null, psmp[ps[qid[ts[i][1] - 1]]], -1);
    } else {
      gadd += ts[i][1];
    }
    let lb, ub;
    [lb, ub] = [0, q + 1];
    while (ub - lb > 1) {
      let mb = lb + ub >> 1;
      if (sorted_ps[sorted_ps.length - 1] < mb - gadd) {
        ub = mb;
        continue;
      }
      let x, y;
      [x, y] = [-1, sorted_ps.length - 1];
      while (y - x > 1) {
        let z = x + y >> 1;
        if (sorted_ps[z] >= mb - gadd) {
          y = z;
        } else {
          x = z;
        }
      }
      let s = root.qry(1, 0, null, y, null);
      if (s >= mb) {
        lb = mb;
      } else {
        ub = mb;
      }
    }
    console.log(lb);
  }

}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));
0