結果
問題 | No.1675 Strange Minimum Query |
ユーザー | nebukuro09 |
提出日時 | 2021-09-10 22:35:13 |
言語 | D (dmd 2.107.1) |
結果 |
AC
|
実行時間 | 803 ms / 2,000 ms |
コード長 | 4,093 bytes |
コンパイル時間 | 1,858 ms |
コンパイル使用メモリ | 120,028 KB |
実行使用メモリ | 29,512 KB |
最終ジャッジ日時 | 2023-09-04 14:05:19 |
合計ジャッジ時間 | 19,353 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 365 ms
14,636 KB |
testcase_04 | AC | 338 ms
18,496 KB |
testcase_05 | AC | 27 ms
9,284 KB |
testcase_06 | AC | 428 ms
15,200 KB |
testcase_07 | AC | 478 ms
19,756 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 273 ms
24,064 KB |
testcase_11 | AC | 90 ms
16,144 KB |
testcase_12 | AC | 307 ms
24,268 KB |
testcase_13 | AC | 342 ms
28,136 KB |
testcase_14 | AC | 460 ms
27,808 KB |
testcase_15 | AC | 445 ms
29,512 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 107 ms
6,888 KB |
testcase_18 | AC | 154 ms
11,156 KB |
testcase_19 | AC | 235 ms
20,936 KB |
testcase_20 | AC | 508 ms
24,564 KB |
testcase_21 | AC | 445 ms
24,344 KB |
testcase_22 | AC | 594 ms
25,084 KB |
testcase_23 | AC | 423 ms
16,408 KB |
testcase_24 | AC | 407 ms
19,536 KB |
testcase_25 | AC | 280 ms
15,564 KB |
testcase_26 | AC | 149 ms
11,816 KB |
testcase_27 | AC | 405 ms
24,236 KB |
testcase_28 | AC | 208 ms
20,652 KB |
testcase_29 | AC | 156 ms
15,556 KB |
testcase_30 | AC | 144 ms
11,628 KB |
testcase_31 | AC | 569 ms
21,788 KB |
testcase_32 | AC | 800 ms
25,904 KB |
testcase_33 | AC | 803 ms
26,000 KB |
testcase_34 | AC | 785 ms
26,072 KB |
testcase_35 | AC | 691 ms
28,516 KB |
testcase_36 | AC | 683 ms
28,184 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; immutable long MOD = 998244353; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto Q = s[1]; auto A = iota(Q).map!(_ => readln.split.map!(to!int).array).array; foreach (a; A) a[0]--, a[1]--; A.sort!"a[2] < b[2]"; auto st = new LazySegmentTree!(long, long, min, (a,b)=>b, (a,b)=>b, (a,b)=>a, 1L<<59, 1L<<59)(N); foreach (a; A) { auto l = a[0]; auto r = a[1]; auto x = a[2].to!long; st.update(l, r, x); } foreach (a; A) { auto l = a[0]; auto r = a[1]; auto x = a[2].to!long; if (st.query(l, r) != x) { writeln(-1); return; } } auto B = N.iota.map!(i => st.query(i, i)).map!(a => a > 10L^^9 ? 10L^^9 : a).array; B.map!(to!string).join(" ").writeln; } /* 参考元: https://github.com/yosupo06/dunkelheit/blob/master/source/dkh/datastructure/segtree.d */ /* T: 取得クエリで取得する値の型 L: 更新クエリで投げる値の型 opTT: 2つの区間の結果をマージする関数 (T, T) -> T opTL: クエリを適用する(作用させる)関数 (T, L) -> T opLL: 2つのクエリをまとめる関数 (L, L) -> L opPrd: (L, int) -> 区間の長さに応じて結果を変化させる関数. 区間和とかに使う (L, int) -> T eT: Tの単位元 eL: Lの単位元 */ /* 1. 区間代入 / 区間min auto st = new LazySegmentTree!(long, long, min, (a,b)=>b, (a,b)=>b, (a,b)=>a, 1L<<59, 1L<<59)(N); 2. 区間加算 / 区間sum auto st = new LazySegmentTree!(long, long, (a,b)=>a+b, (a,b)=>a+b, (a,b)=>a+b, (a,b)=>a*b, 0L, 0L)(N+1); 3. 区間加算 / 区間min auto st = new LazySegmentTree!(long, long, min, (a,b)=>a+b, (a,b)=>a+b, (a,b)=>a, 1L<<59, 0L)(N+1); st.table[] = 0L; 4. 区間代入 / 区間sum auto st = new LazySegmentTree!(long, long, (a,b)=>a+b, (a,b)=>b, (a,b)=>b, (a,b)=>a*b, 0L, 1L<<59)(N+1); いずれもAOJでverify済. 1. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_F 2. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G 3. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_H 4. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_I */ class LazySegmentTree(T, L, alias opTT, alias opTL, alias opLL, alias opPrd, T eT, L eL) { T[] table; L[] lazy_; int n; int size; this(int n) { this.n = n; size = 1; while (size <= n) size <<= 1; size <<= 1; table = new T[](size); lazy_ = new L[](size); table[] = eT; lazy_[] = eL; } void push(int i, int a, int b) { if (lazy_[i] == eL) return; table[i] = opTL(table[i], opPrd(lazy_[i], b - a + 1)); if (i * 2 + 1 < size) { lazy_[i*2] = opLL(lazy_[i*2], lazy_[i]); lazy_[i*2+1] = opLL(lazy_[i*2+1], lazy_[i]); } lazy_[i] = eL; } T query(int l, int r) { if (l > r) return eT; return query(l, r, 1, 0, n-1); } T query(int l, int r, int i, int a, int b) { if (b < l || r < a) return eT; push(i, a, b); if (l <= a && b <= r) { return table[i]; } else { return opTT(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b)); } } void update(int l, int r, L val) { if (l > r) return; update(l, r, 1, 0, n-1, val); } void update(int l, int r, int i, int a, int b, L val) { if (b < l || r < a) { push(i, a, b); } else if (l <= a && b <= r) { lazy_[i] = opLL(lazy_[i], val); push(i, a, b); } else { push(i, a, b); update(l, r, i*2, a, (a+b)/2, val); update(l, r, i*2+1, (a+b)/2+1, b, val); table[i] = opTT(table[i*2], table[i*2+1]); } } }