Submission #1220263
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
import std.typecons;
// import dcomp.foundation, dcomp.scanner;
// import dcomp.algorithm;
// import dcomp.array;
// import dcomp.graph.scc;
int vc;
int[2][] edges;
struct Node {
Node* l, r;
int sz;
int id;
this(int sz) {
this.sz = sz;
id = vc; vc++;
if (sz == 1) return;
l = new Node(sz/2);
r = new Node(sz-sz/2);
}
void addEdge(int a, int b, int p) {
if (a <= 0 && sz <= b) {
edges ~= [p, id];
return;
}
if (b <= 0 || sz <= a) return;
l.addEdge(a, b, p);
r.addEdge(a-sz/2, b-sz/2, p);
}
void set(int k, int p) {
id = vc; vc++;
if (sz == 1) {
edges ~= [id, p];
return;
}
if (k < sz/2) {
l.set(k, p);
} else {
r.set(k-sz/2, p);
}
edges ~= [id, l.id];
edges ~= [id, r.id];
}
}
int main() {
auto sc = new Scanner(stdin);
int n;
sc.read(n);
int[] l, r;
sc.read(l, r);
vc = n;
{
int[2][] f = iota(n).map!(i => [l[i]-i, i].fixed).array
~ iota(n).map!(i => [r[i]-i, n+i].fixed).array;
f.sort!((a, b) => cmp(a[], b[]) == -1);
auto seg = new Node(n);
foreach (ev; f) {
int i = ev[1]%n;
if (ev[1] >= n) {
//que
seg.addEdge(0, i, i);
// writeln("que-left ", i);
} else {
//set
seg.set(i, i);
// writeln("add-left ", i);
}
}
}
{
int[2][] f = iota(n).map!(i => [l[i]+i, i].fixed).array
~ iota(n).map!(i => [r[i]+i, n+i].fixed).array;
f.sort!((a, b) => cmp(a[], b[]) == -1);
auto seg = new Node(n);
foreach (ev; f) {
int i = ev[1]%n;
if (ev[1] >= n) {
//que
seg.addEdge(i+1, n, i);
// writeln("que-right ", i);
} else {
//set
seg.set(i, i);
// writeln("add-right ", i);
}
}
}
// writeln(edges);
alias Edge = Tuple!(int, "to");
Edge[][] g = new Edge[][](vc);
foreach (e; edges) {
g[e[0]] ~= Edge(e[1]);
}
auto sccInfo = scc(g);
// writeln(sccInfo);
int m = sccInfo.groups.length.to!int;
int[][] ng = new int[][](m);
int[] wei = new int[](m);
foreach (i; 0..n) {
wei[sccInfo.id[i]]++;
}
foreach (e; edges) {
int x = sccInfo.id[e[0]];
int y = sccInfo.id[e[1]];
if (x == y) continue;
ng[x] ~= y;
}
// writeln(wei);
// writeln(ng);
foreach_reverse (i; 0..m) {
int ma = 0;
foreach (d; ng[i]) {
ma = max(ma, wei[d]);
}
wei[i] += ma;
}
// writeln(wei);
writeln(wei.maximum);
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/scc.d */
// module dcomp.graph.scc;
// import dcomp.array;
// import dcomp.graph.primitive;
// import dcomp.container.deque;
struct SCC {
int[] id; // vertex id -> scc id
int[][] groups; // scc id -> scc vertexs
this(int n) {
id = new int[n];
}
}
SCC scc(T)(T g) {
import std.range;
import std.algorithm : each, map, min, reverse;
import std.conv : to;
int n = g.length.to!int;
auto sccInfo = SCC(n);
with (sccInfo) {
bool[] inS = new bool[n];
int[] low = new int[n], ord = new int[n]; ord[] = -1;
int time = 0;
Deque!int st;
int bufC = 0;
FastAppender!(int[]) buf; buf.reserve(n);
FastAppender!(int[][]) gBuf;
void dfs(int v) {
low[v] = ord[v] = time++;
st.insertBack(v);
inS[v] = true;
foreach (e; g[v]) {
if (ord[e.to] == -1) {
dfs(e.to);
low[v] = min(low[v], low[e.to]);
} else if (inS[e.to]) {
low[v] = min(low[v], ord[e.to]);
}
}
if (low[v] == ord[v]) {
int p = st.length.to!int - 1;
while (true) {
int u = st.back; st.removeBack;
buf ~= u;
if (u == v) break;
}
auto gr = buf.data[bufC..$];
bufC = buf.length.to!int;
gr.each!(x => inS[x] = false);
gBuf ~= gr;
}
}
foreach (i; 0..n) {
if (ord[i] == -1) dfs(i);
}
groups = gBuf.data;
reverse(groups);
groups.each!((i, v) => v.each!(x => id[x] = i.to!int));
}
return sccInfo;
}
unittest {
import std.algorithm, std.conv, std.stdio, std.range;
import std.random;
import std.typecons;
import std.datetime;
struct E {int to;}
writeln("SCC Random1000");
void f() {
int n = uniform(1, 50);
int p = uniform(1, 50);
E[][] g = new E[][n];
bool[][] naive = new bool[][](n, n);
foreach (i; 0..n) {
foreach (j; 0..n) {
if (i == j) continue;
if (uniform(0, 100) < p) {
g[i] ~= E(j);
naive[i][j] = true;
}
}
}
auto sccInfo = scc(g);
foreach (k; 0..n) {
foreach (i; 0..n) {
foreach (j; 0..n) {
naive[i][j] |= naive[i][k] && naive[k][j];
}
}
}
foreach (i; 0..n) {
int iid = sccInfo.id[i];
assert(sccInfo.groups[iid].find(i).empty == false);
foreach (j; i+1..n) {
bool same = sccInfo.id[i] == sccInfo.id[j];
if (same) {
assert(naive[i][j] && naive[j][i]);
} else {
assert(!naive[i][j] || !naive[j][i]);
if (sccInfo.id[i] < sccInfo.id[j]) {
assert(!naive[j][i]);
} else {
assert(!naive[i][j]);
}
}
}
}
}
auto ti = benchmark!(f)(1000);
writeln(ti[0].msecs, "ms");
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/algorithm.d */
// module dcomp.algorithm;
import std.range.primitives;
import std.traits : isFloatingPoint, isIntegral;
//[0,0,0,...,1,1,1]で、初めて1となる場所を探す。pred(l) == 0, pred(r) == 1と仮定
T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) {
while (r-l > 1) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) {
foreach (i; 0..cnt) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
Rotator!Range rotator(Range)(Range r) {
return Rotator!Range(r);
}
struct Rotator(Range)
if (isForwardRange!Range && hasLength!Range) {
size_t cnt;
Range start, now;
this(Range r) {
cnt = 0;
start = r.save;
now = r.save;
}
this(this) {
start = start.save;
now = now.save;
}
@property bool empty() {
return now.empty;
}
@property auto front() {
assert(!now.empty);
import std.range : take, chain;
return chain(now, start.take(cnt));
}
@property Rotator!Range save() {
return this;
}
void popFront() {
cnt++;
now.popFront;
}
}
E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
import std.algorithm, std.functional;
return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range);
}
ElementType!Range minimum(alias pred = "a < b", Range)(Range range) {
assert(!range.empty, "range must not empty");
auto e = range.front; range.popFront;
return minimum!pred(range, e);
}
E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
import std.algorithm, std.functional;
return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range);
}
ElementType!Range maximum(alias pred = "a < b", Range)(Range range) {
assert(!range.empty, "range must not empty");
auto e = range.front; range.popFront;
return maximum!pred(range, e);
}
unittest {
assert(minimum([2, 1, 3]) == 1);
assert(minimum!"a > b"([2, 1, 3]) == 3);
assert(minimum([2, 1, 3], -1) == -1);
assert(minimum!"a > b"([2, 1, 3], 100) == 100);
assert(maximum([2, 1, 3]) == 3);
assert(maximum!"a > b"([2, 1, 3]) == 1);
assert(maximum([2, 1, 3], 100) == 100);
assert(maximum!"a > b"([2, 1, 3], -1) == -1);
}
bool[ElementType!Range] toMap(Range)(Range r) {
import std.algorithm : each;
bool[ElementType!Range] res;
r.each!(a => res[a] = true);
return res;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/deque.d */
// module dcomp.container.deque;
struct Deque(T) {
import core.exception : RangeError;
import core.memory : GC;
import std.range : ElementType, isInputRange;
import std.traits : isImplicitlyConvertible;
struct Payload {
T *d;
size_t st, length, cap;
@property bool empty() const { return length == 0; }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {
version(assert) if (length <= i) throw new RangeError();
return d[(st+i >= cap) ? (st+i-cap) : st+i];
}
private void expand() {
import std.algorithm : max;
assert(length == cap);
auto nc = max(size_t(4), 2*cap);
T* nd = cast(T*)GC.malloc(nc * T.sizeof);
foreach (i; 0..length) {
nd[i] = this[i];
}
d = nd; st = 0; cap = nc;
}
void clear() {
st = length = 0;
}
void insertFront(T v) {
if (length == cap) expand();
if (st == 0) st += cap;
st--; length++;
this[0] = v;
}
void insertBack(T v) {
if (length == cap) expand();
length++;
this[length-1] = v;
}
void removeFront() {
assert(!empty, "Deque.removeFront: Deque is empty");
st++; length--;
if (st == cap) st = 0;
}
void removeBack() {
assert(!empty, "Deque.removeBack: Deque is empty");
length--;
}
}
struct RangeT(A) {
alias T = typeof(*(A.p));
alias E = typeof(A.p.d[0]);
T *p;
size_t a, b;
@property bool empty() const { return b <= a; }
@property size_t length() const { return b-a; }
@property RangeT save() { return RangeT(p, a, b); }
@property RangeT!(const A) save() const {
return typeof(return)(p, a, b);
}
alias opDollar = length;
@property ref inout(E) front() inout { return (*p)[a]; }
@property ref inout(E) back() inout { return (*p)[b-1]; }
void popFront() {
version(assert) if (empty) throw new RangeError();
a++;
}
void popBack() {
version(assert) if (empty) throw new RangeError();
b--;
}
ref inout(E) opIndex(size_t i) inout { return (*p)[i]; }
RangeT opSlice() { return this.save; }
RangeT opSlice(size_t i, size_t j) {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
RangeT!(const A) opSlice() const { return this.save; }
RangeT!(const A) opSlice(size_t i, size_t j) const {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
}
alias Range = RangeT!Deque;
alias ConstRange = RangeT!(const Deque);
alias ImmutableRange = RangeT!(immutable Deque);
Payload *p;
private void I() { if (!p) p = new Payload(); }
private void C() const {
version(assert) if (!p) throw new RangeError();
}
//some value
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {I;
p = new Payload();
foreach (v; values) {
insertBack(v);
}
}
//range
this(Range)(Range r)
if (isInputRange!Range &&
isImplicitlyConvertible!(ElementType!Range, T) &&
!is(Range == T[])) {I;
p = new Payload();
foreach (v; r) {
insertBack(v);
}
}
@property bool empty() const { return (!p || p.empty); }
@property size_t length() const { return (p ? p.length : 0); }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {C; return (*p)[i]; }
ref inout(T) front() inout {C; return (*p)[0]; }
ref inout(T) back() inout {C; return (*p)[$-1]; }
void clear() { if (p) p.clear(); }
void insertFront(T v) {I; p.insertFront(v); }
void insertBack(T v) {I; p.insertBack(v); }
void removeFront() {C; p.removeFront(); }
void removeBack() {C; p.removeBack(); }
Range opSlice() {I; return Range(p, 0, length); }
}
unittest {
import std.algorithm : equal;
import std.range.primitives : isRandomAccessRange;
import std.container.util : make;
auto q = make!(Deque!int);
assert(isRandomAccessRange!(typeof(q[])));
//insert,remove
assert(equal(q[], new int[](0)));
q.insertBack(1);
assert(equal(q[], [1]));
q.insertBack(2);
assert(equal(q[], [1, 2]));
q.insertFront(3);
assert(equal(q[], [3, 1, 2]) && q.front == 3);
q.removeFront;
assert(equal(q[], [1, 2]) && q.length == 2);
q.insertBack(4);
assert(equal(q[], [1, 2, 4]) && q.front == 1 && q.back == 4 && q[$-1] == 4);
q.insertFront(5);
assert(equal(q[], [5, 1, 2, 4]));
//range
assert(equal(q[][1..3], [1, 2]));
assert(equal(q[][][][], q[]));
//const range
const auto rng = q[];
assert(rng.front == 5 && rng.back == 4);
//reference type
auto q2 = q;
q2.insertBack(6);
q2.insertFront(7);
assert(equal(q[], q2[]) && q.length == q2.length);
//construct with make
auto a = make!(Deque!int)(1, 2, 3);
auto b = make!(Deque!int)([1, 2, 3]);
assert(equal(a[], b[]));
}
unittest {
import std.algorithm : equal;
import std.range.primitives : isRandomAccessRange;
import std.container.util : make;
auto q = make!(Deque!int);
q.clear();
assert(equal(q[], new int[0]));
foreach (i; 0..100) {
q.insertBack(1);
q.insertBack(2);
q.insertBack(3);
q.insertBack(4);
q.insertBack(5);
assert(equal(q[], [1,2,3,4,5]));
q.clear();
assert(equal(q[], new int[0]));
}
}
unittest {
Deque!int a;
Deque!int b;
a.insertFront(2);
assert(b.length == 0);
}
unittest {
import std.algorithm : equal;
import std.range : iota;
Deque!int a;
foreach (i; 0..100) {
a.insertBack(i);
}
assert(equal(a[], iota(100)));
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
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 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;
if (f.eof) return false;
line = lineBuf[];
f.readln(line);
}
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) {
//string or char[10] etc
//todo optimize
auto r = line.findSplitBefore(" ");
x = r[0].strip.dup;
line = r[1];
} else {
auto buf = line.split.map!(to!E).array;
static if (isStaticArray!T) {
//static
assert(buf.length == T.length);
}
x = buf;
line.length = 0;
}
} 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);
}
}
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
fout.writeln("1 2 3");
fout.writeln("ab cde");
fout.writeln("1.0 1.0 2.0");
fout.close;
Scanner sc = new Scanner(File(fileName, "r"));
int a;
int[2] b;
char[2] c;
string d;
double e;
double[] f;
sc.read(a, b, c, d, e, f);
assert(a == 1);
assert(equal(b[], [2, 3]));
assert(equal(c[], "ab"));
assert(equal(d, "cde"));
assert(e == 1.0);
assert(equal(f, [1.0, 2.0]));
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File, writeln;
import std.datetime;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
foreach (i; 0..1_000_000) {
fout.writeln(3*i, " ", 3*i+1, " ", 3*i+2);
}
fout.close;
writeln("Scanner Speed Test(3*1,000,000 int)");
StopWatch sw;
sw.start;
Scanner sc = new Scanner(File(fileName, "r"));
foreach (i; 0..500_000) {
int a, b, c;
sc.read(a, b, c);
assert(a == 3*i);
assert(b == 3*i+1);
assert(c == 3*i+2);
}
foreach (i; 500_000..700_000) {
int[3] d;
sc.read(d);
int a = d[0], b = d[1], c = d[2];
assert(a == 3*i);
assert(b == 3*i+1);
assert(c == 3*i+2);
}
foreach (i; 700_000..1_000_000) {
int[] d;
sc.read(d);
assert(d.length == 3);
int a = d[0], b = d[1], c = d[2];
assert(a == 3*i);
assert(b == 3*i+1);
assert(c == 3*i+2);
}
writeln(sw.peek.msecs, "ms");
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/primitive.d */
// module dcomp.graph.primitive;
import std.range : ElementType;
alias EdgeType(R) = ElementType!(ElementType!R);
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
//fold(for old compiler)
static if (__VERSION__ <= 2070) {
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);
}
}
}
unittest {
import std.stdio;
auto l = [1, 2, 3, 4, 5];
assert(l.fold!"a+b"(10) == 25);
}
}
version (X86) static if (__VERSION__ < 2071) {
int bsf(ulong v) {
foreach (i; 0..64) {
if (v & (1UL << i)) return i;
}
return -1;
}
int bsr(ulong v) {
foreach_reverse (i; 0..64) {
if (v & (1UL << i)) return i;
}
return -1;
}
int popcnt(ulong v) {
int c = 0;
foreach (i; 0..64) {
if (v & (1UL << i)) c++;
}
return c;
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
T[N] fixed(T, int N)(T[N] a) {return a;}
//this is not reference type!(please attention to copy)
struct FastAppender(A) {
import std.algorithm : max;
import std.range.primitives : ElementEncodingType;
import core.stdc.string : memcpy;
private alias T = ElementEncodingType!A;
private T* _data;
private size_t len, cap;
@property size_t length() {return len;}
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* nx = GC.malloc(nlen * T.sizeof);
cap = nlen;
if (len) memcpy(nx, _data, len * T.sizeof);
_data = cast(T*)(nx);
}
void opOpAssign(string op : "~")(T item) {
if (len == cap) {
reserve(max(4, cap*2));
}
_data[len++] = item;
}
void clear() {
len = 0;
}
T[] data() {
return (_data) ? _data[0..len] : null;
}
}
unittest {
import std.stdio, std.algorithm;
auto u = FastAppender!(int[])();
u ~= 4; u ~= 5;
assert(equal(u.data, [4, 5]));
}
Submission Info
Submission Time |
|
Task |
E - 遊園地 |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1200 |
Code Size |
22517 Byte |
Status |
AC |
Exec Time |
952 ms |
Memory |
266720 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
878 ms |
213572 KB |
in10.txt |
AC |
881 ms |
213572 KB |
in11.txt |
AC |
945 ms |
247264 KB |
in12.txt |
AC |
928 ms |
246248 KB |
in13.txt |
AC |
952 ms |
266720 KB |
in14.txt |
AC |
932 ms |
246260 KB |
in15.txt |
AC |
938 ms |
245984 KB |
in16.txt |
AC |
863 ms |
199676 KB |
in17.txt |
AC |
868 ms |
200016 KB |
in18.txt |
AC |
865 ms |
211440 KB |
in19.txt |
AC |
882 ms |
211440 KB |
in2.txt |
AC |
877 ms |
210884 KB |
in20.txt |
AC |
865 ms |
207564 KB |
in21.txt |
AC |
916 ms |
195208 KB |
in22.txt |
AC |
921 ms |
194912 KB |
in23.txt |
AC |
925 ms |
200544 KB |
in24.txt |
AC |
922 ms |
199264 KB |
in25.txt |
AC |
919 ms |
197984 KB |
in26.txt |
AC |
1 ms |
256 KB |
in27.txt |
AC |
1 ms |
256 KB |
in28.txt |
AC |
1 ms |
256 KB |
in29.txt |
AC |
877 ms |
223640 KB |
in3.txt |
AC |
885 ms |
212488 KB |
in30.txt |
AC |
884 ms |
225304 KB |
in31.txt |
AC |
890 ms |
223356 KB |
in32.txt |
AC |
886 ms |
224664 KB |
in33.txt |
AC |
887 ms |
224920 KB |
in4.txt |
AC |
872 ms |
212840 KB |
in5.txt |
AC |
880 ms |
214724 KB |
in6.txt |
AC |
872 ms |
215076 KB |
in7.txt |
AC |
877 ms |
211652 KB |
in8.txt |
AC |
877 ms |
213572 KB |
in9.txt |
AC |
882 ms |
211616 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |