結果
問題 | No.945 YKC饅頭 |
ユーザー | nebukuro09 |
提出日時 | 2019-12-09 13:28:39 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 789 ms / 2,000 ms |
コード長 | 3,988 bytes |
コンパイル時間 | 1,270 ms |
コンパイル使用メモリ | 106,796 KB |
実行使用メモリ | 48,212 KB |
最終ジャッジ日時 | 2023-09-04 03:49:17 |
合計ジャッジ時間 | 17,957 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 3 ms
4,376 KB |
testcase_11 | AC | 3 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 3 ms
4,380 KB |
testcase_14 | AC | 3 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,380 KB |
testcase_17 | AC | 3 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,380 KB |
testcase_22 | AC | 3 ms
4,376 KB |
testcase_23 | AC | 3 ms
4,380 KB |
testcase_24 | AC | 3 ms
4,380 KB |
testcase_25 | AC | 3 ms
4,380 KB |
testcase_26 | AC | 3 ms
4,376 KB |
testcase_27 | AC | 1 ms
4,384 KB |
testcase_28 | AC | 2 ms
4,376 KB |
testcase_29 | AC | 1 ms
4,376 KB |
testcase_30 | AC | 1 ms
4,376 KB |
testcase_31 | AC | 37 ms
6,196 KB |
testcase_32 | AC | 58 ms
8,452 KB |
testcase_33 | AC | 186 ms
20,696 KB |
testcase_34 | AC | 376 ms
27,368 KB |
testcase_35 | AC | 651 ms
41,304 KB |
testcase_36 | AC | 378 ms
33,204 KB |
testcase_37 | AC | 363 ms
28,144 KB |
testcase_38 | AC | 357 ms
25,748 KB |
testcase_39 | AC | 111 ms
13,156 KB |
testcase_40 | AC | 129 ms
16,876 KB |
testcase_41 | AC | 60 ms
8,716 KB |
testcase_42 | AC | 539 ms
36,312 KB |
testcase_43 | AC | 313 ms
28,856 KB |
testcase_44 | AC | 499 ms
35,532 KB |
testcase_45 | AC | 569 ms
40,428 KB |
testcase_46 | AC | 34 ms
8,448 KB |
testcase_47 | AC | 373 ms
26,520 KB |
testcase_48 | AC | 65 ms
9,452 KB |
testcase_49 | AC | 172 ms
16,688 KB |
testcase_50 | AC | 620 ms
43,480 KB |
testcase_51 | AC | 786 ms
47,488 KB |
testcase_52 | AC | 771 ms
48,184 KB |
testcase_53 | AC | 789 ms
47,696 KB |
testcase_54 | AC | 781 ms
48,212 KB |
testcase_55 | AC | 781 ms
48,132 KB |
testcase_56 | AC | 88 ms
12,336 KB |
testcase_57 | AC | 84 ms
12,604 KB |
testcase_58 | AC | 347 ms
38,608 KB |
testcase_59 | AC | 404 ms
42,776 KB |
testcase_60 | AC | 200 ms
25,000 KB |
testcase_61 | AC | 366 ms
39,688 KB |
testcase_62 | AC | 356 ms
38,644 KB |
testcase_63 | AC | 86 ms
11,276 KB |
testcase_64 | AC | 206 ms
25,452 KB |
testcase_65 | AC | 183 ms
21,328 KB |
testcase_66 | AC | 171 ms
22,192 KB |
testcase_67 | AC | 270 ms
31,268 KB |
testcase_68 | AC | 199 ms
23,912 KB |
testcase_69 | AC | 121 ms
17,336 KB |
testcase_70 | AC | 129 ms
16,232 KB |
testcase_71 | AC | 131 ms
17,756 KB |
testcase_72 | AC | 235 ms
27,808 KB |
testcase_73 | AC | 384 ms
38,780 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, std.bitmanip; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto A = iota(M).map!(_ => readln.split).array; alias Tp = Tuple!(int, int); auto st = new LazySegmentTree!(Tp, Tp, min, (a,b)=>b, (a,b)=>b, (a,b)=>a, tuple(1<<29,-1), tuple(1<<29,-1))(N+1); foreach_reverse (i; 0..M) { auto l = A[i][0].to!int - 1; auto r = A[i][1].to!int - 1; auto c = A[i][2].front.to!int; st.update(l, r, tuple(i, c)); } int y, k, c; foreach (i; 0..N) { auto t = st.query(i, i); if (t[1] == 'Y') y++; else if (t[1] == 'K') k++; else if (t[1] == 'C') c++; } writeln(y, " ", k, " ", c); } /* 参考元: 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]); } } }