結果

問題 No.618 labo-index
コンテスト
ユーザー 0w1
提出日時 2018-05-09 18:15:02
言語 JavaScript
(node v25.2.1)
結果
WA  
実行時間 -
コード長 2,050 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 90 ms
コンパイル使用メモリ 6,816 KB
実行使用メモリ 88,108 KB
最終ジャッジ日時 2024-10-13 00:38:11
合計ジャッジ時間 26,720 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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];
  }

  bs(t, lb, rb, s, gadd, uniq_ps) {
    rb = rb || this.sum.length >> 2;
    if (rb - lb == 1) {
      let ss = this.sum[t] + s;
      let sp = uniq_ps[lb] + gadd;
      return [ss, Math.max(0, Math.min(ss, sp))];
    }
    let mb = lb + rb >> 1;
    let rss = this.sum[t << 1 | 1] + s;
    let rsp = uniq_ps[mb] + gadd;
    if (rss >= rsp) return this.bs(t << 1 | 1, mb, rb, s, gadd, uniq_ps);
    return [this.sum[t], Math.max(rss, this.bs(t << 1, lb, mb, s + this.sum[t << 1 | 1], gadd, uniq_ps)[1])];
  }

}

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];
    }
    console.log(root.bs(1, 0, null, 0, gadd, uniq_ps)[1]);
  }

}

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