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 |
|
|
|
|
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 |