Submission #1202851
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;
int main() {
auto sc = new Scanner(stdin);
int n;
sc.read(n);
int[] s = new int[n], t = new int[n];
foreach (i; 0..n) {
sc.read(s[i], t[i]);
}
immutable int M = 100100;
//almost same LazySeg<int, int, ...>(n)
auto seg = LazySeg!(int, int, max, (a,b)=>a+b, (a,b)=>a+b, 0, 0)(M);
foreach (i; 0..n) {
seg.add(s[i], t[i], 1);
}
int mi = 10^^9;
foreach (i; 0..n) {
seg.add(s[i], t[i], -1);
mi = min(mi, seg.sum(0, M));
seg.add(s[i], t[i], 1);
}
writeln(mi);
return 0;
}
struct LazySeg(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL) {
const int n, sz;
T[] d;
L[] lz;
@disable this();
this(int n) {
import std.algorithm : fill;
import core.bitop : bsr;
int lg = n.bsr;
if ((2^^lg) < n) lg++;
this.n = n;
this.sz = 2^^lg;
d = new T[](2*this.sz);
lz = new L[](2*this.sz);
d.fill(eT);
lz.fill(eL);
}
private void lzAdd(int k, L x) {
d[k] = opTL(d[k], x);
lz[k] = opLL(lz[k], x);
}
private void push(int k) {
if (lz[k] == eL) return;
lzAdd(2*k, lz[k]);
lzAdd(2*k+1, lz[k]);
lz[k] = eL;
}
T sum(int a, int b, int l, int r, int k) {
if (b <= l || r <= a) return eT;
if (a <= l && r <= b) return d[k];
push(k);
int md = (l+r)/2;
return opTT(sum(a, b, l, md, 2*k),
sum(a, b, md, r, 2*k+1));
}
T sum(int a, int b) {
assert(0 <= a && a <= b && b <= n);
return sum(a, b, 0, sz, 1);
}
void add(int a, int b, L x, int l, int r, int k) {
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
lzAdd(k, x);
return;
}
push(k);
int md = (l+r)/2;
add(a, b, x, l, md, 2*k);
add(a, b, x, md, r, 2*k+1);
d[k] = opTT(d[2*k], d[2*k+1]);
}
void add(int a, int b, L x) {
assert(0 <= a && a <= b && b <= n);
add(a, b, x, 0, sz, 1);
}
}
/* 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);
}
}
/* 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");
}
Submission Info
Submission Time |
|
Task |
D - 足ゲームII |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
100 |
Code Size |
6956 Byte |
Status |
AC |
Exec Time |
193 ms |
Memory |
4220 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.txt |
All |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
3068 KB |
01-02.txt |
AC |
2 ms |
3708 KB |
01-03.txt |
AC |
2 ms |
3836 KB |
01-04.txt |
AC |
4 ms |
4092 KB |
01-05.txt |
AC |
192 ms |
3580 KB |
01-06.txt |
AC |
191 ms |
3196 KB |
01-07.txt |
AC |
191 ms |
3068 KB |
01-08.txt |
AC |
191 ms |
3068 KB |
01-09.txt |
AC |
191 ms |
3068 KB |
01-10.txt |
AC |
2 ms |
2684 KB |
01-11.txt |
AC |
191 ms |
3068 KB |
01-12.txt |
AC |
191 ms |
3452 KB |
01-13.txt |
AC |
192 ms |
3708 KB |
01-14.txt |
AC |
193 ms |
3324 KB |
01-15.txt |
AC |
6 ms |
4092 KB |
01-16.txt |
AC |
192 ms |
3964 KB |
01-17.txt |
AC |
192 ms |
3836 KB |
01-18.txt |
AC |
192 ms |
3452 KB |
01-19.txt |
AC |
192 ms |
3708 KB |
01-20.txt |
AC |
6 ms |
4092 KB |
01-21.txt |
AC |
190 ms |
3324 KB |
01-22.txt |
AC |
189 ms |
3068 KB |
01-23.txt |
AC |
190 ms |
3452 KB |
01-24.txt |
AC |
149 ms |
4220 KB |
01-25.txt |
AC |
2 ms |
4092 KB |
01-26.txt |
AC |
2 ms |
3964 KB |
01-27.txt |
AC |
121 ms |
3196 KB |
01-28.txt |
AC |
121 ms |
3068 KB |
sample-01.txt |
AC |
2 ms |
3196 KB |
sample-02.txt |
AC |
2 ms |
2684 KB |
sample-03.txt |
AC |
2 ms |
3452 KB |