結果

問題 No.151 セグメントフィッシング
コンテスト
ユーザー te-sh
提出日時 2017-04-27 14:39:52
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,217 ms / 5,000 ms
コード長 2,105 bytes
コンパイル時間 743 ms
コンパイル使用メモリ 110,640 KB
実行使用メモリ 25,336 KB
最終ジャッジ日時 2024-06-12 18:55:47
合計ジャッジ時間 16,207 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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