結果

問題 No.151 セグメントフィッシング
ユーザー te-shte-sh
提出日時 2017-04-27 15:24:34
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 1,478 bytes
コンパイル時間 802 ms
コンパイル使用メモリ 103,988 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 18:56:08
合計ジャッジ時間 1,903 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 AC 6 ms
6,944 KB
testcase_10 AC 6 ms
6,944 KB
testcase_11 AC 5 ms
6,940 KB
testcase_12 AC 21 ms
6,944 KB
testcase_13 AC 21 ms
6,944 KB
testcase_14 AC 21 ms
6,940 KB
testcase_15 AC 20 ms
6,940 KB
testcase_16 AC 20 ms
6,944 KB
testcase_17 AC 16 ms
6,944 KB
testcase_18 AC 16 ms
6,944 KB
testcase_19 AC 24 ms
6,940 KB
testcase_20 AC 24 ms
6,940 KB
testcase_21 AC 17 ms
6,944 KB
testcase_22 AC 18 ms
6,940 KB
testcase_23 AC 19 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap

void main()
{
  auto rd = readln.split.to!(size_t[]), n = rd[0], q = rd[1];

  auto pondL = BiTree!long(n + q + 2);
  auto pondR = BiTree!long(n + q + 2);

  foreach (t; 0..q) {
    auto pl(size_t i) { return i + t + 2; }
    auto pr(size_t i) { return i - t + q + 1; }

    auto rd2 = readln.split;
    switch (rd2[0]) {
    case "L":
      auto y = rd2[1].to!size_t, z = rd2[2].to!long;
      pondL.add(pl(y), z);
      break;
    case "R":
      auto y = rd2[1].to!size_t, z = rd2[2].to!long;
      pondR.add(pr(y), z);
      break;
    case "C":
      auto y = rd2[1].to!size_t, z = rd2[2].to!size_t;
      auto nl = pondL.get(pl(z-1)) - pondL.get(pl(y-1));
      auto nr = pondR.get(pr(z-1)) - pondR.get(pr(y-1));
      writeln(nl + nr);
      break;
    default:
      assert(0);
    }

    auto vl = pondL.get(pl(0)) - pondL.get(pl(-1));
    auto vr = pondR.get(pr(n-1)) - pondR.get(pr(n-2));
    if (vl) {
      pondL.add(pl(0), -vl); pondR.add(pr(-1), vl);
    }
    if (vr) {
      pondR.add(pr(n-1), -vr); pondL.add(pl(n), vr);
    }
  }
}

struct BiTree(T)
{
  T[] b; // buffer
  const size_t s; // size

  this(size_t t)
  {
    s = t;
    b = new T[](s + 1);
  }

  pure T get(size_t i) const
  {
    return i ? b[i] + get(i - (i & -i)) : 0;
  }

  void add(size_t i, T v)
  {
    if (i > s) return;
    b[i] += v;
    add(i + (i & -i), v);
  }
}
0