結果

問題 No.151 セグメントフィッシング
ユーザー te-shte-sh
提出日時 2017-04-27 14:39:52
言語 D
(dmd 2.105.2)
結果
AC  
実行時間 1,720 ms / 5,000 ms
コード長 2,105 bytes
コンパイル時間 744 ms
コンパイル使用メモリ 95,740 KB
実行使用メモリ 25,848 KB
最終ジャッジ日時 2023-09-03 13:02:58
合計ジャッジ時間 21,565 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 5 ms
4,380 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 5 ms
4,376 KB
testcase_08 AC 223 ms
7,776 KB
testcase_09 AC 220 ms
7,740 KB
testcase_10 AC 222 ms
7,760 KB
testcase_11 AC 223 ms
7,728 KB
testcase_12 AC 1,687 ms
15,240 KB
testcase_13 AC 1,671 ms
15,244 KB
testcase_14 AC 1,674 ms
25,764 KB
testcase_15 AC 1,632 ms
25,848 KB
testcase_16 AC 1,681 ms
15,200 KB
testcase_17 AC 1,379 ms
15,212 KB
testcase_18 AC 1,387 ms
15,216 KB
testcase_19 AC 1,720 ms
15,224 KB
testcase_20 AC 1,701 ms
15,244 KB
testcase_21 AC 1,630 ms
15,308 KB
testcase_22 AC 1,629 ms
15,304 KB
testcase_23 AC 500 ms
4,376 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 = new Pond!long(n);
  auto pondR = new Pond!long(n);

  foreach (_; 0..q) {
    auto rd2 = readln.split;
    switch (rd2[0]) {
    case "L":
      pondL.add(rd2[1].to!size_t, rd2[2].to!long);
      break;
    case "R":
      pondR.add(rd2[1].to!size_t, rd2[2].to!long);
      break;
    case "C":
      auto nl = pondL.sum(rd2[1].to!size_t, rd2[2].to!size_t);
      auto nr = pondR.sum(rd2[1].to!size_t, rd2[2].to!size_t);
      writeln(nl + nr);
      break;
    default:
      assert(0);
    }

    auto vl = pondL.rotL();
    auto vr = pondR.rotR();
    pondR.add(0, vl);
    pondL.add(n-1, vr);
  }
}

class Pond(T)
{
  const qsz = 100;

  size_t n;
  size_t qn;
  DList!T[] qs;
  T[] mas;

  this(size_t n)
  {
    this.n = n;
    qn = (n + qsz - 1) / qsz;

    qs = new DList!T[](qn);
    foreach (i; 0..qn-1)
      qs[i] = DList!T(T.init.repeat.take(qsz));
    qs[$-1] = DList!T(T.init.repeat.take(n - (qn - 1) * qsz));

    mas = new T[](qn);
  }

  void add(size_t i, T v)
  {
    auto q = qs[i / qsz].array;
    q[i % qsz] += v;
    qs[i / qsz] = DList!T(q);
    mas[i / qsz] += v;
  }

  T rotR()
  {
    qs[0].insertFront(T.init);
    foreach (i; 1..qn) {
      auto v = qs[i-1].back; qs[i-1].removeBack();
      qs[i].insertFront(v);
      mas[i - 1] -= v;
      mas[i] += v;
    }
    auto r = qs[$-1].back; qs[$-1].removeBack();
    mas[$-1] -= r;
    return r;
  }

  T rotL()
  {
    qs[$-1].insertBack(T.init);
    foreach_reverse (i; 0..qn-1) {
      auto v = qs[i+1].front; qs[i+1].removeFront();
      qs[i].insertBack(v);
      mas[i+1] -= v;
      mas[i] += v;
    }
    auto r = qs[0].front; qs[0].removeFront();
    mas[0] -= r;
    return r;
  }

  T sum(size_t i, size_t j)
  {
    auto k = j - 1;
    auto i2 = i / qsz, k2 = k / qsz;
    auto r = mas[i2..k2+1].sum;
    r -= qs[i2].array[0..(i % qsz)].sum;
    r -= qs[k2].array[(k % qsz)+1..$].sum;
    return r;
  }
}
0