結果
問題 | No.619 CardShuffle |
ユーザー |
![]() |
提出日時 | 2017-12-19 01:52:26 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 131 ms / 3,000 ms |
コード長 | 18,717 bytes |
コンパイル時間 | 1,420 ms |
コンパイル使用メモリ | 144,544 KB |
実行使用メモリ | 8,844 KB |
最終ジャッジ日時 | 2024-06-12 23:11:45 |
合計ジャッジ時間 | 5,472 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 35 |
ソースコード
/+ dub.sdl:name "A"dependency "dcomp" version=">=0.8.0"+/import std.stdio, std.algorithm, std.range, std.conv;// import dcomp.foundation, dcomp.scanner;import std.typecons;// import dcomp.modint;// import dcomp.segtree.simpleseg;alias Mint = ModInt!(10^^9 + 7);struct N {bool havePlus;Mint l, m, r;}N merge(N l, N r) {N x;x.havePlus = l.havePlus | r.havePlus;x.l = l.l;if (!l.havePlus) x.l *= r.l;x.r = r.r;if (!r.havePlus) x.r *= l.r;x.m = l.m + r.m;if (l.havePlus && r.havePlus) x.m += l.r * r.l;return x;}immutable N e = N(false, Mint(1), Mint(0), Mint(1));int main() {Scanner sc = new Scanner(stdin);int n;sc.read(n);auto seg = SimpleSeg!(N, merge, e)(n);foreach (i; 0..n) {if (i % 2 == 0) {int x;sc.read(x);seg[i] = N(false, Mint(x), Mint(0), Mint(x));} else {char c;sc.read(c);if (c == '+') {seg[i] = N(true, Mint(1), Mint(0), Mint(1));} else {seg[i] = N(false, Mint(1), Mint(0), Mint(1));}}}int q;sc.read(q);foreach (i; 0..q) {char c; int x, y;sc.read(c, x, y);if (c == '?') {//getx--;auto u = seg[x..y].sum;writeln((u.havePlus ? u.l + u.m + u.r : u.l));} else {//setx--; y--;auto l = seg[x], r = seg[y];seg[x] = r; seg[y] = l;}}return 0;}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/modint.d */// module dcomp.modint;// import dcomp.numeric.primitive;struct ModInt(uint MD) if (MD < int.max) {import std.conv : to;uint v;this(int v) {this(long(v));}this(long v) {this.v = (v%MD+MD)%MD;}static auto normS(uint x) {return (x<MD)?x:x-MD;}static auto make(uint x) {ModInt m; m.v = x; return m;}auto opBinary(string op:"+")(ModInt r) const {return make(normS(v+r.v));}auto opBinary(string op:"-")(ModInt r) const {return make(normS(v+MD-r.v));}auto opBinary(string op:"*")(ModInt r) const {return make((ulong(v)*r.v%MD).to!uint);}auto opBinary(string op:"/")(ModInt r) const {return this*inv(r);}auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");}static ModInt inv(ModInt x) {return ModInt(extGcd!int(x.v, MD)[0]);}string toString() const {return v.to!string;}}struct DModInt(string name) {import std.conv : to;static uint MD;uint v;this(int v) {this(long(v));}this(long v) {this.v = ((v%MD+MD)%MD).to!uint;}static auto normS(uint x) {return (x<MD)?x:x-MD;}static auto make(uint x) {DModInt m; m.MD = MD; m.v = x; return m;}auto opBinary(string op:"+")(DModInt r) const {return make(normS(v+r.v));}auto opBinary(string op:"-")(DModInt r) const {return make(normS(v+MD-r.v));}auto opBinary(string op:"*")(DModInt r) const {return make((ulong(v)*r.v%MD).to!uint);}auto opBinary(string op:"/")(DModInt r) const {return this*inv(r);}auto opOpAssign(string op)(DModInt r) {return mixin ("this=this"~op~"r");}static DModInt inv(DModInt x) {return DModInt(extGcd!int(x.v, MD)[0]);}string toString() {return v.to!string;}}template isModInt(T) {const isModInt =is(T : ModInt!MD, uint MD) || is(S : DModInt!S, string s);}T[] factTable(T)(size_t length) if (isModInt!T) {import std.range : take, recurrence;import std.array : array;return T(1).recurrence!((a, n) => a[n-1]*T(n)).take(length).array;}T[] invFactTable(T)(size_t length) if (isModInt!T) {import std.algorithm : map, reduce;import std.range : take, recurrence, iota;import std.array : array;auto res = new T[length];res[$-1] = T(1) / iota(1, length).map!T.reduce!"a*b";foreach_reverse (i, v; res[0..$-1]) {res[i] = res[i+1] * T(i+1);}return res;}T[] invTable(T)(size_t length) if (isModInt!T) {auto f = factTable!T(length);auto invf = invFactTable!T(length);auto res = new T[length];foreach (i; 1..length) {res[i] = invf[i] * f[i-1];}return res;}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */// module dcomp.numeric.primitive;import std.traits;import std.bigint;Unqual!T pow(T, U)(T x, U n)if (!isFloatingPoint!T && (isIntegral!U || is(U == BigInt))) {return pow(x, n, T(1));}Unqual!T pow(T, U, V)(T x, U n, V e)if ((isIntegral!U || is(U == BigInt)) && is(Unqual!T == Unqual!V)) {Unqual!T b = x, v = e;Unqual!U m = n;while (m) {if (m & 1) v *= b;b *= b;m /= 2;}return v;}T powMod(T, U, V)(T x, U n, V md)if (isIntegral!U || is(U == BigInt)) {T r = T(1);while (n) {if (n & 1) r = (r*x)%md;x = (x*x)%md;n >>= 1;}return r % md;}// import dcomp.int128;ulong ulongPowMod(U)(ulong x, U n, ulong md)if (isIntegral!U || is(U == BigInt)) {x %= md;ulong r = 1;while (n) {if (n & 1) {r = mul128(r, x).mod128(md);}x = mul128(x, x).mod128(md);n >>= 1;}return r % md;}T lcm(T)(in T a, in T b) {import std.numeric : gcd;return a / gcd(a,b) * b;}T[3] extGcd(T)(in T a, in T b)if (!isIntegral!T || isSigned!T){if (b==0) {return [T(1), T(0), a];} else {auto e = extGcd(b, a%b);return [e[1], e[0]-a/b*e[1], e[2]];}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/stackpayload.d */// module dcomp.container.stackpayload;struct StackPayload(T, size_t MINCAP = 4) if (MINCAP >= 1) {import core.exception : RangeError;private T* _data;private uint len, cap;@property bool empty() const { return len == 0; }@property size_t length() const { return len; }alias opDollar = length;inout(T)[] data() inout { return (_data) ? _data[0..len] : null; }ref inout(T) opIndex(size_t i) inout {version(assert) if (len <= i) throw new RangeError();return _data[i];}ref inout(T) front() inout { return this[0]; }ref inout(T) back() inout { return this[$-1]; }void reserve(size_t newCap) {import core.memory : GC;import core.stdc.string : memcpy;import std.conv : to;if (newCap <= cap) return;void* newData = GC.malloc(newCap * T.sizeof);cap = newCap.to!uint;if (len) memcpy(newData, _data, len * T.sizeof);_data = cast(T*)(newData);}void free() {import core.memory : GC;GC.free(_data);}void clear() {len = 0;}void insertBack(T item) {import std.algorithm : max;if (len == cap) reserve(max(cap * 2, MINCAP));_data[len++] = item;}alias opOpAssign(string op : "~") = insertBack;void removeBack() {assert(!empty, "StackPayload.removeBack: Stack is empty");len--;}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/ldc/inline.d */// module dcomp.ldc.inline;version(LDC) {pragma(LDC_inline_ir) R inlineIR(string s, R, P...)(P);}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/segtree/simpleseg.d */// module dcomp.segtree.simpleseg;// import dcomp.segtree.primitive;import std.functional : binaryFun;alias SimpleSeg(T, alias opTT, T eT, alias Engine = SimpleSegEngine) =SegTree!(Engine, T, binaryFun!opTT, eT);struct SimpleSegEngine(T, alias opTT, T eT) {alias DataType = T;alias LazyType = void;alias BinSearch = binSearchSimple;uint n, sz, lg;T[] d;@property uint length() const {return n;}this(uint n) {import std.algorithm : each;this.n = n;while ((2^^lg) < n) lg++;sz = 2^^lg;d = new T[](2*sz);d.each!((ref x) => x = eT);}this(T[] first) {import std.conv : to;import std.algorithm : each;n = first.length.to!uint;if (n == 0) return;while ((2^^lg) < n) lg++;sz = 2^^lg;d = new T[](2*sz);d.each!((ref x) => x = eT);foreach (i; 0..n) {d[sz+i] = first[i];}foreach_reverse (i; 1..sz) {update(i);}}pragma(inline):void update(uint k) {d[k] = opTT(d[2*k], d[2*k+1]);}T single(uint k) {return d[k+sz];}void singleSet(uint k, T x) {k += sz;d[k] = x;foreach (uint i; 1..lg+1) {update(k>>i);}}T sum(uint a, uint b) {assert(0 <= a && a <= b && b <= n);T sml = eT, smr = eT;a += sz; b += sz;while (a < b) {if (a & 1) sml = opTT(sml, d[a++]);if (b & 1) smr = opTT(d[--b], smr);a >>= 1; b >>= 1;}return opTT(sml, smr);}}int binSearchSimple(bool rev, alias pred, TR)(TR t, int a, int b) {import std.traits : TemplateArgsOf;alias args = TemplateArgsOf!TR;alias opTT = args[1];auto x = args[2];with (t) {static if (!rev) {if (pred(x)) return a-1;int pos = a;void f(int a, int b, int l, int r, int k) {if (b <= l || r <= a) return;if (a <= l && r <= b && !pred(opTT(x, d[k]))) {x = opTT(x, d[k]);pos = r;return;}if (l+1 == r) return;int md = (l+r)/2;f(a, b, l, md, 2*k);if (pos >= md) f(a, b, md, r, 2*k+1);}f(a, b, 0, sz, 1);return pos;} else {if (pred(x)) return b;int pos = b-1;void f(int a, int b, int l, int r, int k) {if (b <= l || r <= a) return;if (a <= l && r <= b && !pred(opTT(x, d[k]))) {x = opTT(d[k], x);pos = l-1;return;}if (l+1 == r) return;int md = (l+r)/2;f(a, b, md, r, 2*k+1);if (pos < md) f(a, b, l, md, 2*k);}f(a, b, 0, sz, 1);return pos;}}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */// module dcomp.scanner;// import dcomp.container.stackpayload;class Scanner {import std.stdio : File;import std.conv : to;import std.range : front, popFront, array, ElementType;import std.array : split;import std.traits : isSomeChar, isStaticArray, isArray;import std.algorithm : map;File f;this(File f) {this.f = f;}char[512] lineBuf;char[] line;private bool succW() {import std.range.primitives : empty, front, popFront;import std.ascii : isWhite;while (!line.empty && line.front.isWhite) {line.popFront;}return !line.empty;}private bool succ() {import std.range.primitives : empty, front, popFront;import std.ascii : isWhite;while (true) {while (!line.empty && line.front.isWhite) {line.popFront;}if (!line.empty) break;line = lineBuf[];f.readln(line);if (!line.length) return false;}return true;}private bool readSingle(T)(ref T x) {import std.algorithm : findSplitBefore;import std.string : strip;import std.conv : parse;if (!succ()) return false;static if (isArray!T) {alias E = ElementType!T;static if (isSomeChar!E) {auto r = line.findSplitBefore(" ");x = r[0].strip.dup;line = r[1];} else static if (isStaticArray!T) {foreach (i; 0..T.length) {bool f = succW();assert(f);x[i] = line.parse!E;}} else {StackPayload!E buf;while (succW()) {buf ~= line.parse!E;}x = buf.data;}} else {x = line.parse!T;}return true;}int read(T, Args...)(ref T x, auto ref Args args) {if (!readSingle(x)) return 0;static if (args.length == 0) {return 1;} else {return 1 + read(args);}}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */// module dcomp.foundation;static if (__VERSION__ <= 2070) {/*Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.dCopyright: Andrei Alexandrescu 2008-.License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).*/template fold(fun...) if (fun.length >= 1) {auto fold(R, S...)(R r, S seed) {import std.algorithm : reduce;static if (S.length < 2) {return reduce!fun(seed, r);} else {import std.typecons : tuple;return reduce!fun(tuple(seed), r);}}}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/int128.d */// module dcomp.int128;version(LDC) {// import dcomp.ldc.inline;}version(LDC) version(X86_64) {version = LDC_IR;}ulong[2] mul128(ulong a, ulong b) {ulong[2] res;version(LDC_IR) {ulong upper, lower;inlineIR!(`%r0 = zext i64 %0 to i128%r1 = zext i64 %1 to i128%r2 = mul i128 %r1, %r0%r3 = trunc i128 %r2 to i64%r4 = lshr i128 %r2, 64%r5 = trunc i128 %r4 to i64store i64 %r3, i64* %2store i64 %r5, i64* %3`, void)(a, b, &lower, &upper);return [lower, upper];} else version(D_InlineAsm_X86_64) {ulong upper, lower;asm {mov RAX, a;mul b;mov lower, RAX;mov upper, RDX;}return [lower, upper];} else {ulong B = 2UL^^32;ulong[2] a2 = [a % B, a / B];ulong[2] b2 = [b % B, b / B];ulong[4] c;foreach (i; 0..2) {foreach (j; 0..2) {c[i+j] += a2[i] * b2[j] % B;c[i+j+1] += a2[i] * b2[j] / B;}}foreach (i; 0..3) {c[i+1] += c[i] / B;c[i] %= B;}return [c[0] + c[1] * B, c[2] + c[3] * B];}}ulong div128(ulong[2] a, ulong b) {version(LDC_IR) {return inlineIR!(`%r0 = zext i64 %0 to i128%r1 = zext i64 %1 to i128%r2 = shl i128 %r1, 64%r3 = add i128 %r0, %r2%r4 = zext i64 %2 to i128%r5 = udiv i128 %r3, %r4%r6 = trunc i128 %r5 to i64ret i64 %r6`,ulong)(a[0], a[1], b);} else version(D_InlineAsm_X86_64) {ulong upper = a[1], lower = a[0];ulong res;asm {mov RDX, upper;mov RAX, lower;div b;mov res, RAX;}return res;} else {if (b == 1) return a[0];while (!(b & (1UL << 63))) {a[1] <<= 1;if (a[0] & (1UL << 63)) a[1] |= 1;a[0] <<= 1;b <<= 1;}ulong ans = 0;foreach (i; 0..64) {bool up = (a[1] & (1UL << 63)) != 0;a[1] <<= 1;if (a[0] & (1UL << 63)) a[1] |= 1;a[0] <<= 1;ans <<= 1;if (up || b <= a[1]) {a[1] -= b;ans++;}}return ans;}}ulong mod128(ulong[2] a, ulong b) {version(D_InlineAsm_X86_64) {ulong upper = a[1], lower = a[0];ulong res;asm {mov RDX, upper;mov RAX, lower;div b;mov res, RDX;}return res;} else {return a[0] - div128(a, b) * b;}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/segtree/primitive.d */// module dcomp.segtree.primitive;import std.conv : to;struct SegTree(alias E, Args...) {import std.traits : ReturnType;alias Engine = E!Args;alias T = Engine.DataType;alias L = Engine.LazyType;Engine eng;this(size_t n) { eng = Engine(n.to!uint); }this(T[] first) { eng = Engine(first); }@property size_t length() const { return eng.length(); }@property size_t opDollar() const { return eng.length(); }struct Range {Engine* eng;size_t start, end;@property const(T) sum() {return eng.sum(start.to!uint, end.to!uint);}}const(T) opIndex(size_t k) {assert(0 <= k && k < eng.length());return eng.single(k.to!uint);}void opIndexAssign(T x, size_t k) {assert(0 <= k && k < eng.length());eng.singleSet(k.to!uint, x);}size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) {assert(0 <= start && start <= end && end <= eng.length());return [start, end];}Range opIndex(size_t[2] rng) {return Range(&eng, rng[0].to!uint, rng[1].to!uint);}static if (!is(L == void)) {void opIndexOpAssign(string op : "+")(L x, size_t[2] rng) {eng.add(rng[0].to!uint, rng[1].to!uint, x);}}}import std.traits : isInstanceOf;ptrdiff_t binSearchLeft(alias pred, TR)(TR t, ptrdiff_t a, ptrdiff_t b)if (isInstanceOf!(SegTree, TR)) {return TR.Engine.BinSearch!(false, pred)(t.eng, a.to!int, b.to!int);}ptrdiff_t binSearchRight(alias pred, TR)(TR t, ptrdiff_t a, ptrdiff_t b)if (isInstanceOf!(SegTree, TR)) {return TR.Engine.BinSearch!(true, pred)(t.eng, a.to!int, b.to!int);}/*This source code generated by dcomp and include dcomp's source code.dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)*/