Submission #1198581
Source Code Expand
/+ dub.sdl:
name "D"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.algorithm;
// import dcomp.scanner;
// import dcomp.algorithm;
struct Node {
alias NP = Node*;
NP l, r;
int sz;
int v = -1, lz = -1;
void lzdata(int x) {
v = x; lz = x;
}
void push() {
if (lz != -1) {
l.lzdata(lz);
r.lzdata(lz);
lz = -1;
}
}
void set(int a, int b, int x) {
if (b <= 0 || sz <= a) return;
if (a <= 0 && sz <= b) {
lzdata(x);
return;
}
push();
l.set(a, b, x);
r.set(a-sz/2, b-sz/2, x);
}
int get(int k) {
if (sz == 1) {
return v;
}
push();
if (k < sz/2) {
return l.get(k);
} else {
return r.get(k - sz/2);
}
}
this(int sz) {
this.sz = sz;
if (sz == 1) return;
l = new Node(sz/2);
r = new Node(sz-sz/2);
}
}
int main() {
auto sc = new Scanner(stdin);
int n; long k;
sc.read(n, k);
long[] a = new long[](n);
bool[] b = new bool[](n);
long base = 0;
foreach (i; 0..n) {
int f;
sc.read(a[i], f);
b[i] = (f == 1) ? true : false;
if (b[i] && 2*a[i] > k) {
writeln("-1");
return 0;
}
base += 2*a[i];
a[i] %= k;
}
long ba = 0;
long[2][] v;
foreach_reverse (i; 0..n) {
a[i] *= 2; a[i] %= k;
if (b[i]) {
v ~= [ba, (ba+a[i])%k];
}
ba += a[i]; ba %= k;
}
// writeln(v);
long[] di = [0];
foreach (p; v) {
di ~= p[0]; di ~= p[1];
}
di.sort!"a<b"; di = di.uniq.array;
int m = di.length.to!int;
auto tr = new Node(m);
int getI(long x) {
return binSearch!(i => di[i] >= x)(-1, di.length.to!int);
}
long[] dp = new long[n];
long getD(int idx) {
int u = tr.get(idx);
if (u == -1) return 0;
long a = di[idx];
return (v[u][1]-a+k)%k + dp[u];
}
foreach (int i, p; v) {
int u = tr.get(getI(p[1]));
dp[i] = getD(getI(p[1]));
int l = getI(p[0]);
int r = getI(p[1]);
if (l < r) {
tr.set(l+1, r, i);
} else {
tr.set(l+1, m, i);
tr.set(0, r, i);
}
}
writeln(base + iota(m).map!getD.minimum);
return 0;
}
/* 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/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;
}
Submission Info
Submission Time |
|
Task |
F - Train Service Planning |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1700 |
Code Size |
9440 Byte |
Status |
AC |
Exec Time |
169 ms |
Memory |
12796 KB |
Judge Result
Set Name |
Sample |
All |
subtask |
subtask2 |
Score / Max Score |
0 / 0 |
700 / 700 |
500 / 500 |
500 / 500 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in101.txt, in102.txt, in103.txt, in104.txt, in105.txt, in106.txt, in107.txt, in108.txt, in109.txt, in11.txt, in110.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, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask |
sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask2 |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
2 ms |
380 KB |
in10.txt |
AC |
104 ms |
8828 KB |
in101.txt |
AC |
73 ms |
8060 KB |
in102.txt |
AC |
75 ms |
8444 KB |
in103.txt |
AC |
68 ms |
6908 KB |
in104.txt |
AC |
78 ms |
11388 KB |
in105.txt |
AC |
80 ms |
11260 KB |
in106.txt |
AC |
78 ms |
8060 KB |
in107.txt |
AC |
74 ms |
9980 KB |
in108.txt |
AC |
69 ms |
4604 KB |
in109.txt |
AC |
80 ms |
10108 KB |
in11.txt |
AC |
104 ms |
10236 KB |
in110.txt |
AC |
78 ms |
11516 KB |
in12.txt |
AC |
103 ms |
8828 KB |
in13.txt |
AC |
98 ms |
9468 KB |
in14.txt |
AC |
105 ms |
9084 KB |
in15.txt |
AC |
100 ms |
10492 KB |
in16.txt |
AC |
101 ms |
9596 KB |
in17.txt |
AC |
103 ms |
10236 KB |
in18.txt |
AC |
102 ms |
10236 KB |
in19.txt |
AC |
101 ms |
10364 KB |
in2.txt |
AC |
104 ms |
9852 KB |
in20.txt |
AC |
101 ms |
8572 KB |
in21.txt |
AC |
85 ms |
9852 KB |
in22.txt |
AC |
83 ms |
9980 KB |
in23.txt |
AC |
87 ms |
10108 KB |
in24.txt |
AC |
87 ms |
9468 KB |
in25.txt |
AC |
34 ms |
4220 KB |
in26.txt |
AC |
34 ms |
4220 KB |
in27.txt |
AC |
33 ms |
3964 KB |
in28.txt |
AC |
35 ms |
3836 KB |
in3.txt |
AC |
103 ms |
9340 KB |
in4.txt |
AC |
106 ms |
10108 KB |
in5.txt |
AC |
89 ms |
9212 KB |
in6.txt |
AC |
102 ms |
10236 KB |
in7.txt |
AC |
90 ms |
7164 KB |
in8.txt |
AC |
13 ms |
2940 KB |
in9.txt |
AC |
107 ms |
10236 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |
sample4.txt |
AC |
1 ms |
256 KB |
sub2in1.txt |
AC |
1 ms |
256 KB |
sub2in10.txt |
AC |
1 ms |
256 KB |
sub2in11.txt |
AC |
1 ms |
256 KB |
sub2in12.txt |
AC |
1 ms |
256 KB |
sub2in13.txt |
AC |
1 ms |
256 KB |
sub2in14.txt |
AC |
1 ms |
256 KB |
sub2in15.txt |
AC |
1 ms |
256 KB |
sub2in16.txt |
AC |
1 ms |
256 KB |
sub2in17.txt |
AC |
1 ms |
256 KB |
sub2in18.txt |
AC |
1 ms |
256 KB |
sub2in19.txt |
AC |
1 ms |
256 KB |
sub2in2.txt |
AC |
1 ms |
256 KB |
sub2in20.txt |
AC |
1 ms |
256 KB |
sub2in21.txt |
AC |
1 ms |
256 KB |
sub2in22.txt |
AC |
1 ms |
256 KB |
sub2in23.txt |
AC |
1 ms |
256 KB |
sub2in24.txt |
AC |
1 ms |
256 KB |
sub2in3.txt |
AC |
1 ms |
256 KB |
sub2in4.txt |
AC |
1 ms |
256 KB |
sub2in5.txt |
AC |
1 ms |
256 KB |
sub2in6.txt |
AC |
1 ms |
256 KB |
sub2in7.txt |
AC |
1 ms |
256 KB |
sub2in8.txt |
AC |
1 ms |
256 KB |
sub2in9.txt |
AC |
1 ms |
256 KB |
subin1.txt |
AC |
166 ms |
11900 KB |
subin10.txt |
AC |
166 ms |
11388 KB |
subin101.txt |
AC |
139 ms |
11644 KB |
subin102.txt |
AC |
123 ms |
12284 KB |
subin103.txt |
AC |
117 ms |
12540 KB |
subin104.txt |
AC |
115 ms |
12412 KB |
subin105.txt |
AC |
114 ms |
10748 KB |
subin106.txt |
AC |
107 ms |
11260 KB |
subin107.txt |
AC |
128 ms |
11132 KB |
subin108.txt |
AC |
131 ms |
11260 KB |
subin109.txt |
AC |
125 ms |
11388 KB |
subin11.txt |
AC |
158 ms |
12028 KB |
subin12.txt |
AC |
163 ms |
12796 KB |
subin13.txt |
AC |
166 ms |
11644 KB |
subin14.txt |
AC |
165 ms |
11260 KB |
subin15.txt |
AC |
161 ms |
11772 KB |
subin16.txt |
AC |
163 ms |
11004 KB |
subin17.txt |
AC |
154 ms |
11644 KB |
subin18.txt |
AC |
156 ms |
12284 KB |
subin19.txt |
AC |
158 ms |
12028 KB |
subin2.txt |
AC |
162 ms |
10748 KB |
subin20.txt |
AC |
160 ms |
11260 KB |
subin201.txt |
AC |
1 ms |
256 KB |
subin21.txt |
AC |
44 ms |
4348 KB |
subin22.txt |
AC |
44 ms |
4348 KB |
subin23.txt |
AC |
45 ms |
4348 KB |
subin24.txt |
AC |
45 ms |
4348 KB |
subin3.txt |
AC |
168 ms |
12156 KB |
subin4.txt |
AC |
142 ms |
9724 KB |
subin5.txt |
AC |
162 ms |
11388 KB |
subin6.txt |
AC |
125 ms |
12668 KB |
subin7.txt |
AC |
19 ms |
2684 KB |
subin8.txt |
AC |
14 ms |
3068 KB |
subin9.txt |
AC |
169 ms |
11004 KB |