結果
問題 | No.1673 Lamps on a line |
ユーザー |
|
提出日時 | 2021-09-10 21:58:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 1,776 ms |
コンパイル使用メモリ | 181,260 KB |
実行使用メモリ | 19,432 KB |
最終ジャッジ日時 | 2024-06-11 23:52:00 |
合計ジャッジ時間 | 4,288 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 |
ソースコード
#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; } }