Submission #1559838
Source Code Expand
/+ dub.sdl: name "A" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner; import std.typecons; int main() { auto sc = new Scanner(stdin); long x; int k; long[] r; int q; long[] t, a; sc.read(x, k, r, q); t = new long[q]; a = new long[q]; iota(q).each!(i => sc.read(t[i], a[i])); alias Q = Tuple!(long, int); Q[] ev; foreach (i; 0..k) { ev ~= Q(r[i], -1); } foreach (i; 0..q) { ev ~= Q(t[i], i); } ev.sort!"a<b"; long d = 0, e = 0, f = x, g = x; bool suc = true; long tm = 0; long[] res = new long[q]; foreach (que; ev) { long di = que[0] - tm; int ty = que[1]; if (suc) { d -= di; g -= di; if (d < 0) { e += -d; d = 0; } if (g <= 0) { d = 0; e = 0; f = 0; g = 0; } } else { d += di; g += di; if (x < g) { f -= g-x; g = x; } if (x <= d) { d = x; e = x; f = x; g = x; } } // writefln("time %d: %d %d %d %d", tm+di, d, e, f, g); if (ty == -1) { //reverse suc = !suc; } else { if (a[ty] <= e) { res[ty] = d; } else if (f <= a[ty]) { res[ty] = g; } else { res[ty] = d + a[ty] - e; } } tm = que[0]; } writeln(res.map!(to!string).join("\n")); return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; 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); } } } } version (X86) static if (__VERSION__ < 2071) { import core.bitop : bsf, bsr, popcnt; 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/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) { 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) { 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); } } }
Submission Info
Submission Time | |
---|---|
Task | F - Sandglass |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 700 |
Code Size | 4799 Byte |
Status | AC |
Exec Time | 105 ms |
Memory | 13176 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 1 ms | 256 KB |
0_001.txt | AC | 1 ms | 256 KB |
0_002.txt | AC | 1 ms | 256 KB |
1_003.txt | AC | 84 ms | 12548 KB |
1_004.txt | AC | 87 ms | 12280 KB |
1_005.txt | AC | 91 ms | 10932 KB |
1_006.txt | AC | 86 ms | 12036 KB |
1_007.txt | AC | 89 ms | 11512 KB |
1_008.txt | AC | 92 ms | 12212 KB |
1_009.txt | AC | 86 ms | 12932 KB |
1_010.txt | AC | 91 ms | 11896 KB |
1_011.txt | AC | 92 ms | 11316 KB |
1_012.txt | AC | 87 ms | 11652 KB |
1_013.txt | AC | 89 ms | 11128 KB |
1_014.txt | AC | 98 ms | 12340 KB |
1_015.txt | AC | 87 ms | 13060 KB |
1_016.txt | AC | 88 ms | 12152 KB |
1_017.txt | AC | 95 ms | 12340 KB |
1_018.txt | AC | 89 ms | 12292 KB |
1_019.txt | AC | 93 ms | 12152 KB |
1_020.txt | AC | 98 ms | 11828 KB |
1_021.txt | AC | 98 ms | 11524 KB |
1_022.txt | AC | 92 ms | 12536 KB |
1_023.txt | AC | 94 ms | 11956 KB |
1_024.txt | AC | 99 ms | 11268 KB |
1_025.txt | AC | 93 ms | 12408 KB |
1_026.txt | AC | 98 ms | 12212 KB |
1_027.txt | AC | 101 ms | 11524 KB |
1_028.txt | AC | 104 ms | 13176 KB |
1_029.txt | AC | 99 ms | 12340 KB |
1_030.txt | AC | 102 ms | 12676 KB |
1_031.txt | AC | 105 ms | 13176 KB |
1_032.txt | AC | 98 ms | 12724 KB |
1_033.txt | AC | 44 ms | 6908 KB |
1_034.txt | AC | 48 ms | 6908 KB |
1_035.txt | AC | 90 ms | 12356 KB |
1_036.txt | AC | 47 ms | 9084 KB |
1_037.txt | AC | 50 ms | 7036 KB |
1_038.txt | AC | 97 ms | 12384 KB |
1_039.txt | AC | 48 ms | 6652 KB |
1_040.txt | AC | 51 ms | 7292 KB |
1_041.txt | AC | 101 ms | 12596 KB |