結果
問題 | No.2762 Counting and Deleting |
ユーザー | Yudai0606Nazo |
提出日時 | 2024-05-18 08:39:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,777 ms / 4,000 ms |
コード長 | 2,201 bytes |
コンパイル時間 | 5,245 ms |
コンパイル使用メモリ | 281,912 KB |
実行使用メモリ | 33,304 KB |
最終ジャッジ日時 | 2024-05-18 08:40:17 |
合計ジャッジ時間 | 20,641 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 1,734 ms
33,304 KB |
testcase_08 | AC | 1,703 ms
33,232 KB |
testcase_09 | AC | 1,737 ms
33,292 KB |
testcase_10 | AC | 1,777 ms
33,224 KB |
testcase_11 | AC | 1,356 ms
33,196 KB |
testcase_12 | AC | 1,381 ms
33,288 KB |
testcase_13 | AC | 1,370 ms
33,228 KB |
testcase_14 | AC | 1,374 ms
33,236 KB |
testcase_15 | AC | 1,403 ms
33,220 KB |
testcase_16 | AC | 1,409 ms
33,268 KB |
ソースコード
#include <bits/stdc++.h> #include <cassert> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; //using mint = modint1000000007; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repu(i, s, t) for (int i = (int)(s); i < (int)(t); i++) #define repd(i, s, t) for (int i = (int)(s)-1; i >= (int)(t); i--) #define all(v) v.begin(), v.end() template<typename T> bool chmax(T &a, const T b) { if(a >= b) return false; a = b; return true; } template<typename T> bool chmin(T &a, const T b) { if(a <= b) return false; a = b; return true; } template<typename T> istream& operator>>(istream &in, vector<T> &a) { for(T &x: a) in >> x; return in; } template<typename T> ostream& operator<<(ostream &out, const vector<T> &a) { for(const T &x: a) out << x << ' '; return out; } const int di[] = {1, 0, -1, 0, 1, 1, -1, -1, 0}; const int dj[] = {0, 1, 0, -1, -1, 1, 1, -1, 0}; struct S { bool zero_ex, one_ex; vector<vector<mint>> val; S() : zero_ex(false), one_ex(false), val(2, vector<mint>(3)) {} S(bool x) : zero_ex(!x), one_ex(x), val(2, vector<mint>(3)) { val[int(x)] = {1, 1, 1}; } }; S op(S l, S r) { S res; rep(i, 2) rep(j, 3) res.val[i][j] = l.val[i][j] + l.val[i][0] * r.val[0][j] + l.val[i][1] * r.val[1][j]; if(!l.zero_ex) res.val[0] = r.val[0]; if(!l.one_ex) res.val[1] = r.val[1]; if(r.zero_ex) rep(i, 2) res.val[i][0] -= l.val[i][0]; if(r.one_ex) rep(i, 2) res.val[i][1] -= l.val[i][1]; res.zero_ex = l.zero_ex || r.zero_ex; res.one_ex = l.one_ex || r.one_ex; return res; } S e() { return S(); } using F = bool; S mapping(F l, S r) { if(l) return e(); return r; } F composition(F l, F r) { return l || r; } F id() { return false; } int main() { int n, q; string s; cin >> n >> q >> s; lazy_segtree<S, op, e, F, mapping, composition, id> lst(n); rep(i, n) lst.set(i, S(s[i]-'0')); while(q--) { int t, l, r; cin >> t >> l >> r; l--; if(t == 1) { lst.apply(l, r, true); } else { cout << lst.prod(l, r).val[1][2].val() << '\n'; } } return 0; }