結果

問題 No.618 labo-index
ユーザー 0w10w1
提出日時 2018-05-09 18:15:02
言語 JavaScript
(node v21.7.1)
結果
WA  
実行時間 -
コード長 2,050 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 5,504 KB
実行使用メモリ 88,108 KB
最終ジャッジ日時 2024-04-21 02:09:12
合計ジャッジ時間 26,718 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
38,784 KB
testcase_01 AC 64 ms
38,912 KB
testcase_02 AC 64 ms
38,784 KB
testcase_03 AC 61 ms
38,784 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 919 ms
71,408 KB
testcase_37 WA -
testcase_38 AC 59 ms
38,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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