結果
| 問題 |
No.2292 Interval Union Find
|
| コンテスト | |
| ユーザー |
 Daylight
|
| 提出日時 | 2023-05-06 10:30:28 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 378 ms / 5,000 ms |
| コード長 | 5,784 bytes |
| コンパイル時間 | 3,353 ms |
| コンパイル使用メモリ | 283,904 KB |
| 実行使用メモリ | 29,676 KB |
| 最終ジャッジ日時 | 2024-06-22 17:50:45 |
| 合計ジャッジ時間 | 21,754 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 44 |
ソースコード
public import std;
DList!string scan_buffer;
DList!char char_buffer;
static this() {
scan_buffer = DList!(string)();
char_buffer = DList!(char)();
}
void cin()() {
}
void cin(T, A...)(ref T a, ref A tail) {
import std.traits : isArray;
static if (typeof(a).stringof == "string") {
if (!char_buffer.empty) {
a = char_buffer.array.map!(x => x.to!string).join();
char_buffer.clear();
} else {
while (scan_buffer.empty) {
foreach (t; readln.split) {
if (t.length == 0) {
continue;
}
scan_buffer.insert(t);
}
}
auto token = scan_buffer.front;
scan_buffer.removeFront();
a = token;
}
} else static if (typeof(a).stringof == "char") {
if (!char_buffer.empty) {
a = char_buffer.front();
char_buffer.removeFront();
} else {
while (scan_buffer.empty) {
foreach (t; readln.split) {
if (t.length == 0) {
continue;
}
scan_buffer.insert(t);
}
}
auto token = scan_buffer.front;
scan_buffer.removeFront();
a = token[0];
if (token.length > 1) {
foreach (c; token[1 .. $]) {
char_buffer.insertBack(c);
}
}
}
} else static if (typeof(a).stringof == "char[]") {
if (a.length == 0) {
string token;
cin(token);
foreach (c; token) {
a ~= c;
}
} else {
foreach (ref v; a) {
cin(v);
}
}
} else static if (isArray!(typeof(a))) {
foreach (ref v; a) {
cin(v);
}
} else static if (isTuple!(typeof(a))) {
foreach (i, _; a) {
cin(a[i]);
}
} else {
if (!char_buffer.empty) {
writeln(char_buffer.array.map!(x => x.to!string));
a = char_buffer.array.map!(x => x.to!string).join().to!T;
char_buffer.clear();
} else {
while (scan_buffer.empty) {
foreach (t; readln.split) {
if (t.length == 0) {
continue;
}
scan_buffer.insert(t);
}
}
auto token = scan_buffer.front;
scan_buffer.removeFront();
a = token.to!T;
}
}
cin(tail);
}
bool chmin(T)(ref T a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
bool chmax(T)(ref T a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
alias PQueue(T = long, alias less = "a<b") = BinaryHeap!(Array!T, less);
import std;
class IntervalUnionFind {
private:
alias P = Tuple!(long, "l", long, "r");
const long INF = (long.max - 100);
public:
RedBlackTree!(P, "a.r!=b.r?a.r<b.r:a<b") set;
this() {
set = new RedBlackTree!(P, "a.r!=b.r?a.r<b.r:a<b")();
}
P merge(long l, long r) {
auto it = set.upperBound(P(-INF, l));
auto vec = new P[](0);
foreach (p; it) {
if (max(l, p.l) > min(r, p.r)) {
break;
}
l.chmin(p.l);
r.chmax(p.r);
vec ~= p;
}
foreach (p; vec) {
set.removeKey(p);
}
set.insert(P(l, r));
return P(l, r);
}
void unmerge(long l, long r) {
auto it = set.upperBound(P(-INF, l));
auto vec = new P[](0);
auto vec2 = new P[](0);
foreach (p; it) {
if (max(l, p.l) > min(r, p.r)) {
break;
}
if (p.l < l) {
vec2 ~= (P(p.l, l));
}
if (r < p.r) {
vec2 ~= (P(r, p.r));
}
vec ~= p;
}
foreach (p; vec) {
set.removeKey(p);
}
foreach (p; vec2) {
set.insert(p);
}
}
Nullable!P getInterval(long i) {
auto it = set.upperBound(P(-INF, i));
if (it.empty) {
return Nullable!P();
} else if (it.front.l <= i && i <= it.front.r) {
return it.front.nullable;
} else {
return Nullable!P();
}
}
bool opBinary(string op)(long i) {
return !getInterval(i).isNull();
}
}
void main() {
int N, Q;
cin(N, Q);
auto dsu = new IntervalUnionFind();
foreach (_; 0 .. Q) {
int k;
cin(k);
if (k == 1) {
int l, r;
cin(l, r);
dsu.merge(l, r);
} else if (k == 2) {
int l, r;
cin(l, r);
dsu.unmerge(l, r);
} else if (k == 3) {
int u, v;
cin(u, v);
auto p = dsu.getInterval(u);
if (p.isNull()) {
if (u == v) {
1.writeln;
} else {
0.writeln;
}
} else {
auto pp = p.get();
if (pp.l <= v && v <= pp.r) {
1.writeln;
} else {
0.writeln;
}
}
} else if (k == 4) {
int u;
cin(u);
auto p = dsu.getInterval(u);
if (p.isNull()) {
1.writeln;
} else {
auto pp = p.get();
(pp.r - pp.l + 1).writeln;
}
}
}
}