結果

問題 No.619 CardShuffle
ユーザー yosupotyosupot
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/+ 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 == '?') {
//get
x--;
auto u = seg[x..y].sum;
writeln((u.havePlus ? u.l + u.m + u.r : u.l));
} else {
//set
x--; 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.d
Copyright: 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 i64
store i64 %r3, i64* %2
store 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 i64
ret 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)
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0