結果
問題 | No.945 YKC饅頭 |
ユーザー | Mister |
提出日時 | 2020-08-04 17:01:30 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 631 ms / 2,000 ms |
コード長 | 4,176 bytes |
コンパイル時間 | 1,376 ms |
コンパイル使用メモリ | 107,704 KB |
実行使用メモリ | 11,528 KB |
最終ジャッジ日時 | 2023-10-12 20:48:34 |
合計ジャッジ時間 | 17,648 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,352 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 3 ms
4,352 KB |
testcase_04 | AC | 1 ms
4,352 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 3 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 3 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,352 KB |
testcase_13 | AC | 3 ms
4,348 KB |
testcase_14 | AC | 2 ms
4,348 KB |
testcase_15 | AC | 1 ms
4,348 KB |
testcase_16 | AC | 2 ms
4,348 KB |
testcase_17 | AC | 2 ms
4,348 KB |
testcase_18 | AC | 2 ms
4,352 KB |
testcase_19 | AC | 2 ms
4,348 KB |
testcase_20 | AC | 2 ms
4,352 KB |
testcase_21 | AC | 2 ms
4,348 KB |
testcase_22 | AC | 3 ms
4,352 KB |
testcase_23 | AC | 3 ms
4,352 KB |
testcase_24 | AC | 3 ms
4,348 KB |
testcase_25 | AC | 3 ms
4,352 KB |
testcase_26 | AC | 3 ms
4,352 KB |
testcase_27 | AC | 2 ms
4,348 KB |
testcase_28 | AC | 2 ms
4,352 KB |
testcase_29 | AC | 1 ms
4,348 KB |
testcase_30 | AC | 2 ms
4,348 KB |
testcase_31 | AC | 30 ms
5,112 KB |
testcase_32 | AC | 45 ms
7,256 KB |
testcase_33 | AC | 151 ms
11,340 KB |
testcase_34 | AC | 294 ms
7,300 KB |
testcase_35 | AC | 513 ms
11,340 KB |
testcase_36 | AC | 275 ms
4,352 KB |
testcase_37 | AC | 271 ms
4,348 KB |
testcase_38 | AC | 267 ms
5,076 KB |
testcase_39 | AC | 86 ms
7,168 KB |
testcase_40 | AC | 95 ms
11,376 KB |
testcase_41 | AC | 47 ms
7,360 KB |
testcase_42 | AC | 422 ms
7,384 KB |
testcase_43 | AC | 222 ms
4,352 KB |
testcase_44 | AC | 393 ms
11,304 KB |
testcase_45 | AC | 460 ms
7,280 KB |
testcase_46 | AC | 28 ms
7,380 KB |
testcase_47 | AC | 302 ms
7,292 KB |
testcase_48 | AC | 52 ms
4,348 KB |
testcase_49 | AC | 138 ms
7,268 KB |
testcase_50 | AC | 494 ms
7,188 KB |
testcase_51 | AC | 613 ms
11,364 KB |
testcase_52 | AC | 603 ms
11,260 KB |
testcase_53 | AC | 629 ms
11,280 KB |
testcase_54 | AC | 631 ms
11,256 KB |
testcase_55 | AC | 621 ms
11,376 KB |
testcase_56 | AC | 67 ms
11,316 KB |
testcase_57 | AC | 65 ms
11,264 KB |
testcase_58 | AC | 221 ms
11,320 KB |
testcase_59 | AC | 255 ms
11,272 KB |
testcase_60 | AC | 131 ms
11,528 KB |
testcase_61 | AC | 228 ms
11,384 KB |
testcase_62 | AC | 224 ms
11,360 KB |
testcase_63 | AC | 68 ms
11,364 KB |
testcase_64 | AC | 138 ms
11,276 KB |
testcase_65 | AC | 128 ms
11,340 KB |
testcase_66 | AC | 121 ms
11,308 KB |
testcase_67 | AC | 183 ms
11,364 KB |
testcase_68 | AC | 134 ms
11,452 KB |
testcase_69 | AC | 87 ms
11,316 KB |
testcase_70 | AC | 94 ms
11,352 KB |
testcase_71 | AC | 94 ms
11,520 KB |
testcase_72 | AC | 161 ms
11,324 KB |
testcase_73 | AC | 253 ms
11,348 KB |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <functional> template <class T, class E> struct LazySegmentTree { using DMerger = std::function<T(T, T)>; using OMerger = std::function<E(E, E)>; using Applier = std::function<T(T, E, int)>; int length; T d_unit; E o_unit; std::vector<T> dat; std::vector<E> ope; DMerger dmerge; OMerger omerge; Applier app; explicit LazySegmentTree(int n, T d_unit, E o_unit, DMerger dmerge, OMerger omerge, Applier app) : length(1), d_unit(d_unit), o_unit(o_unit), dmerge(dmerge), omerge(omerge), app(app) { while (length < n) length <<= 1; dat.assign(length * 2, d_unit); ope.assign(length * 2, o_unit); } template <class Container> explicit LazySegmentTree(const Container& elems, T d_unit, E o_unit, DMerger dmerge, OMerger omerge, Applier app) : length(1), d_unit(d_unit), o_unit(o_unit), dmerge(dmerge), omerge(omerge), app(app) { int n = elems.size(); while (length < n) length <<= 1; dat.assign(length * 2, d_unit); ope.assign(length * 2, o_unit); std::copy(elems.begin(), elems.end(), dat.begin() + length); for (int nidx = length - 1; nidx >= 1; --nidx) { T vl = dat[nidx * 2 + 0]; T vr = dat[nidx * 2 + 1]; dat[nidx] = dmerge(vl, vr); } } void propagate(int nidx, int len) { if (ope[nidx] == o_unit) return; // propagate if (len > 1) { ope[nidx * 2 + 0] = omerge(ope[nidx * 2 + 0], ope[nidx]); ope[nidx * 2 + 1] = omerge(ope[nidx * 2 + 1], ope[nidx]); } // update data dat[nidx] = app(dat[nidx], ope[nidx], len); ope[nidx] = o_unit; } void update(int ql, int qr, E e, int nidx, int nl, int nr) { propagate(nidx, nr - nl); if (nr <= ql || qr <= nl) return; if (ql <= nl && nr <= qr) { ope[nidx] = omerge(ope[nidx], e); propagate(nidx, nr - nl); return; } int nm = (nl + nr) / 2; update(ql, qr, e, nidx * 2 + 0, nl, nm); update(ql, qr, e, nidx * 2 + 1, nm, nr); // update data dat[nidx] = dmerge(dat[nidx * 2 + 0], dat[nidx * 2 + 1]); } void update(int ql, int qr, E e) { return update(ql, qr, e, 1, 0, length); } T fold(int ql, int qr, int nidx, int nl, int nr) { propagate(nidx, nr - nl); if (nr <= ql || qr <= nl) return d_unit; if (ql <= nl && nr <= qr) return dat[nidx]; int nm = (nl + nr) / 2; T vl = fold(ql, qr, nidx * 2 + 0, nl, nm); T vr = fold(ql, qr, nidx * 2 + 1, nm, nr); return dmerge(vl, vr); } T fold(int ql, int qr) { return fold(ql, qr, 1, 0, length); } T get(int idx) { return fold(idx, idx + 1); } T fold_all() { return fold(0, length); } }; void solve() { int n, q; std::cin >> n >> q; LazySegmentTree<std::pair<int, char>, std::pair<int, char>> seg( n, std::make_pair(q, '$'), std::make_pair(q, '$'), [](auto a, auto b) { return std::min(a, b); }, [](auto e, auto f) { return std::min(e, f); }, [](auto a, auto e, int) { return std::min(a, e); }); for (int i = 0; i < q; ++i) { int l, r; char t; std::cin >> l >> r >> t; seg.update(--l, r, std::make_pair(i, t)); } std::vector<int> ans(3, 0); for (int i = 0; i < n; ++i) { auto t = seg.get(i).second; for (int j = 0; j < 3; ++j) { if (t == "YKC"[j]) ++ans[j]; } } for (auto a : ans) std::cout << a << " "; std::cout << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }