結果
問題 | No.1673 Lamps on a line |
ユーザー | ecottea |
提出日時 | 2021-09-10 21:58:07 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 362 ms / 2,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 1,854 ms |
コンパイル使用メモリ | 180,392 KB |
実行使用メモリ | 19,340 KB |
最終ジャッジ日時 | 2023-09-02 17:21:24 |
合計ジャッジ時間 | 4,785 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,372 KB |
testcase_01 | AC | 1 ms
4,368 KB |
testcase_02 | AC | 86 ms
4,372 KB |
testcase_03 | AC | 84 ms
4,372 KB |
testcase_04 | AC | 153 ms
4,368 KB |
testcase_05 | AC | 9 ms
4,368 KB |
testcase_06 | AC | 134 ms
4,372 KB |
testcase_07 | AC | 251 ms
18,352 KB |
testcase_08 | AC | 13 ms
17,492 KB |
testcase_09 | AC | 327 ms
6,692 KB |
testcase_10 | AC | 355 ms
10,832 KB |
testcase_11 | AC | 38 ms
11,112 KB |
testcase_12 | AC | 362 ms
19,340 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <atcoder/modint> #include <atcoder/lazysegtree> using namespace std; using namespace atcoder; using mint = modint998244353; using val = pair<mint, int>; using func = pair<mint, mint>; val op(val a, val b) { mint a1, b1; int a2, b2; tie(a1, a2) = a; tie(b1, b2) = b; return make_pair(a1 + b1, a2 + b2); } val e() { return make_pair(mint(0), 0); } val mapping(func f, val x) { mint x1, b, c; int x2; tie(x1, x2) = x; tie(b, c) = f; return make_pair(x1 * b + c * x2, x2); } func composition(func f, func g) { mint b1, c1, b2, c2; tie(b1, c1) = f; tie(b2, c2) = g; return make_pair(b1 * b2, b1 * c2 + c1); } func id() { return make_pair(mint(1), mint(0)); } int main() { int n, q; cin >> n >> q; vector<val> a(n); for (int i = 0; i < n; i++) { a.at(i) = make_pair(mint(0), 1); } lazy_segtree<val, op, e, func, mapping, composition, id> seg(a); for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; l--; seg.apply(l, r, make_pair(-1, 1)); cout << seg.prod(0, n).first.val() << endl; } }