Submission #1755120


Source Code Expand

import std.algorithm, std.conv, std.range, std.stdio, std.string;

const mod = 10^^9+7;
alias mint = FactorRing!mod;
alias Mat = mint[][];
const u0 = mint(0), u1 = mint(1);
const unit1 = [[u1,u0],[u0,u1]];
const unit2 = [[u1,u0,u0,u0,u0],[u0,u1,u0,u0,u0],[u0,u0,u1,u0,u0],[u0,u0,u0,u1,u0],[u0,u0,u0,u0,u1]];

struct P { long r, c; }

void main()
{
  auto rd1 = readln.split.to!(long[]), h = rd1[0], w = rd1[1];
  auto n = readln.chomp.to!size_t;

  auto p = new P[](n);
  foreach (i; 0..n) {
    auto rd2 = readln.splitter;
    auto r = rd2.front.to!long; rd2.popFront();
    auto c = rd2.front.to!long;
    p[i] = P(r-1, c);
  }

  auto pc = [0L] ~ p.map!"a.c".array.sort().uniq.array ~ [w+1];
  auto npc = pc.length;

  int[long] ap;
  long[] nm;
  auto i = 0;

  foreach (j; 1..npc) {
    auto c = pc[j], s = pc[j] - pc[j-1];
    if (s == 1) {
      ap[c] = i++;
      nm ~= 1;
    } else if (s == 2) {
      ap[c-1] = i++;
      ap[c] = i++;
      nm ~= [1, 1];
    } else {
      i++;
      ap[c-1] = i++;
      ap[c] = i++;
      nm ~= [s-2, 1, 1];
    }
  }

  foreach (ref pi; p)
    pi.c = ap[pi.c];

  nm = nm[0..$-1];
  auto nnm = nm.length;

  if (h == 1) calc1(w, nnm, p, nm);
  else        calc2(w, nnm, p, nm);
}

auto calc1(long w, size_t n, P[] p, long[] nm)
{
  auto q0 = [[u1,u1],[u1,u0]];
  auto q1 = [[u1,u1],[u0,u0]];

  auto st = SegmentTree!(Mat, unit1, matMul)(n);
  foreach (i; 0..n-1) st[n-i-1] = repeatedSquare!(Mat, matMul, long)(q0, nm[i], unit1);
  st[0] = cast(Mat)q1;

  auto cap = new bool[](n+1);
  cap[n] = true;

  auto update(long c)
  {
    st[n-c-1] = cast(Mat)(cap[c] || cap[c+1] ? q1 : q0);
  }

  foreach (pi; p) {
    auto c = pi.c;
    cap[c] = !cap[c];
    if (c > 0) update(c-1);
    update(c);
    auto t = st[0..$];
    writeln(t[0][0]);
  }
}

auto calc2(long w, size_t n, P[] p, long[] nm)
{
  auto q0 = [[u1,u1,u1,u1,u1],[u1,u1,u0,u0,u0],[u1,u1,u0,u1,u0],[u1,u1,u1,u0,u0],[u1,u1,u0,u0,u0]];

  auto q(int[] i)
  {
    auto q1 = q0.dup;
    foreach (j; i)
      q1[j] = [u0,u0,u0,u0,u0];
    return cast(Mat)q1;
  }

  auto st = SegmentTree!(Mat, unit2, matMul)(n);
  foreach (i; 0..n-1) st[n-i-1] = repeatedSquare!(Mat, matMul, long)(q0, nm[i], unit2);
  st[0] = q([2,3,4]);

  auto cap = new bool[][](2, n+1);
  cap[0][n] = cap[1][n] = true;

  auto update(long c)
  {
    int[] j;
    if (cap[0][c] || cap[1][c]) j ~= 1;
    if (cap[0][c] || cap[0][c+1]) j ~= 2;
    if (cap[1][c] || cap[1][c+1]) j ~= 3;
    if (cap[0][c] || cap[1][c] || cap[0][c+1] || cap[1][c+1]) j ~= 4;
    st[n-c-1] = q(j);
  }

  foreach (pi; p) {
    auto r = pi.r, c = pi.c;
    cap[r][c] = !cap[r][c];
    if (c > 0) update(c-1);
    update(c);
    auto t = st[0..$];
    writeln(t[0][0] + t[1][0]);
  }
}

pure T repeatedSquare(T, alias pred = "a * b", U)(const T a, U n)
{
  return repeatedSquare(a, n, T(1));
}

pure T repeatedSquare(T, alias pred = "a * b", U)(const T a, U n, const T init)
{
  import std.functional;
  alias predFun = binaryFun!pred;

  if (n == 0) return cast(T)init;

  T r = cast(T)init, b = cast(T)a;
  while (n > 0) {
    if ((n & 1) == 1)
      r = predFun(r, a);
    b = predFun(a, a);
    n >>= 1;
  }

  return r;
}

T[][] matMul(T)(const T[][] a, const T[][] b)
{
  auto l = b.length, m = a.length, n = b[0].length;
  auto c = new T[][](m, n);
  foreach (i; 0..m) {
    static if (T.init != 0) c[i][] = 0;
    foreach (j; 0..n)
      foreach (k; 0..l)
        c[i][j] += a[i][k] * b[k][j];
  }
  return c;
}

struct SegmentTree(T, T unit, alias pred = "a + b")
{
  import core.bitop, std.functional;
  alias predFun = binaryFun!pred;

  const size_t n, an;
  T[] buf;

  this(size_t n)
  {
    this.n = n;
    an = (1 << ((n - 1).bsr + 1));
    buf = new T[](an * 2);
    static if (T.init != unit) {
      buf[] = unit;
    }
  }

  this(T[] init)
  {
    this(init.length);
    buf[an..an+n][] = init[];
    foreach_reverse (i; 1..an)
      buf[i] = predFun(buf[i*2], buf[i*2+1]);
  }

  void opIndexAssign(T val, size_t i)
  {
    buf[i += an] = val;
    while (i /= 2)
      buf[i] = predFun(buf[i * 2], buf[i * 2 + 1]);
  }

  pure T opSlice(size_t l, size_t r) const
  {
    l += an; r += an;
    T r1 = unit, r2 = unit;
    while (l != r) {
      if (l % 2) r1 = predFun(r1, buf[l++]);
      if (r % 2) r2 = predFun(buf[--r], r2);
      l /= 2; r /= 2;
    }
    return predFun(r1, r2);
  }

  pure size_t opDollar() { return n; }
  pure T opIndex(size_t i) { return buf[i + an]; }
}

struct FactorRing(int m, bool pos = false)
{
  version(BigEndian) {
    union { long vl; struct { int vi2; int vi; } }
  } else {
    union { long vl; int vi; }
  }

  static init() { return FactorRing!(m, pos)(0); }

  @property int toInt() { return vi; }
  alias toInt this;

  this(int v) { vi = v; }
  this(int v, bool runMod) { vi = runMod ? mod(v) : v; }
  this(long v) { vi = mod(v); }

  ref FactorRing!(m, pos) opAssign(int v) { vi = v; return this; }

  pure auto mod(int v) const
  {
    static if (pos) return v % m;
    else return (v % m + m) % m;
  }

  pure auto mod(long v) const
  {
    static if (pos) return cast(int)(v % m);
    else return cast(int)((v % m + m) % m);
  }

  static if (!pos) {
    pure auto opUnary(string op: "-")() const { return FactorRing!(m, pos)(mod(-vi)); }
  }

  static if (m < int.max / 2) {
    pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vi + rhs)); }
    pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vi - rhs)); }
  } else {
    pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vl + rhs)); }
    pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vl - rhs)); }
  }
  pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!(m, pos)(mod(vl * rhs)); }

  pure auto opBinary(string op)(FactorRing!(m, pos) rhs) const
  if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.vi); }

  static if (m < int.max / 2) {
    auto opOpAssign(string op: "+")(int rhs) { vi = mod(vi + rhs); }
    auto opOpAssign(string op: "-")(int rhs) { vi = mod(vi - rhs); }
  } else {
    auto opOpAssign(string op: "+")(int rhs) { vi = mod(vl + rhs); }
    auto opOpAssign(string op: "-")(int rhs) { vi = mod(vl - rhs); }
  }
  auto opOpAssign(string op: "*")(int rhs) { vi = mod(vl * rhs); }

  auto opOpAssign(string op)(FactorRing!(m, pos) rhs)
    if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.vi); }
}

Submission Info

Submission Time
Task D - コンセント
User tesh
Language D (DMD64 v2.070.1)
Score 0
Code Size 6748 Byte
Status WA
Exec Time 6498 ms
Memory 445948 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 10 0 / 30 0 / 60
Status
AC × 2
AC × 2
WA × 10
AC × 3
WA × 19
AC × 3
WA × 29
Set Name Test Cases
Sample subtask0_sample-01.txt, subtask0_sample-02.txt
Subtask1 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt
Subtask2 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt
Subtask3 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt AC 1 ms 256 KB
subtask0_sample-02.txt AC 1 ms 256 KB
subtask1_01.txt WA 2 ms 380 KB
subtask1_02.txt WA 4 ms 636 KB
subtask1_03.txt WA 7 ms 1276 KB
subtask1_04.txt WA 15 ms 3836 KB
subtask1_05.txt WA 354 ms 41468 KB
subtask1_06.txt WA 359 ms 45820 KB
subtask1_07.txt WA 73 ms 14204 KB
subtask1_08.txt WA 446 ms 50556 KB
subtask1_09.txt WA 436 ms 50556 KB
subtask1_10.txt WA 421 ms 50556 KB
subtask2_01.txt WA 297 ms 32508 KB
subtask2_02.txt WA 320 ms 35324 KB
subtask2_03.txt AC 115 ms 8700 KB
subtask2_04.txt WA 83 ms 15740 KB
subtask2_05.txt WA 141 ms 21500 KB
subtask2_06.txt WA 690 ms 60412 KB
subtask2_07.txt WA 675 ms 57340 KB
subtask2_08.txt WA 142 ms 21500 KB
subtask2_09.txt WA 693 ms 61180 KB
subtask2_10.txt WA 699 ms 63100 KB
subtask3_01.txt WA 6421 ms 445180 KB
subtask3_02.txt WA 6117 ms 444924 KB
subtask3_03.txt WA 1266 ms 150012 KB
subtask3_04.txt WA 6372 ms 444284 KB
subtask3_05.txt WA 1329 ms 148476 KB
subtask3_06.txt WA 1321 ms 148220 KB
subtask3_07.txt WA 6460 ms 445564 KB
subtask3_08.txt WA 6498 ms 444412 KB
subtask3_09.txt WA 6372 ms 445948 KB
subtask3_10.txt WA 6450 ms 444412 KB