結果
問題 | No.2498 OX Operations |
ユーザー | Kude |
提出日時 | 2023-10-07 00:45:16 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,956 bytes |
コンパイル時間 | 3,881 ms |
コンパイル使用メモリ | 279,564 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-26 17:37:59 |
合計ジャッジ時間 | 22,688 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 4 ms
6,944 KB |
testcase_12 | AC | 12 ms
6,944 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 583 ms
6,940 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; using mint = modint998244353; template <class F, F (*composition)(F, F), F (*id)()> struct dual_segtree { public: dual_segtree() : dual_segtree(0) {} explicit dual_segtree(int n) : dual_segtree(std::vector<F>(n, id())) {} explicit dual_segtree(const std::vector<F>& v) : _n(int(v.size())) { auto ceil_log2 = [](int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; }; log = ceil_log2(_n); size = 1 << log; lz = std::vector<F>(2 * size, id()); for (int i = 0; i < _n; i++) lz[size + i] = v[i]; } void set(int p, F x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); lz[p] = x; } F get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return lz[p]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); lz[p] = composition(f, lz[p]); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } } void push_all() { for (int i = 1; i < size; i++) push(i); } F get_raw(int p) { assert(0 <= p && p < _n); return lz[size + p]; } private: int _n, size, log; std::vector<F> lz; void all_apply(int k, F f) { lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; struct F { int a, b; }; F compositon(F f, F g) { // fa(gax + gb) + fb return {f.a & g.a, (f.a & g.b) ^ f.b}; } F id() { return {~0, 0}; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; VI m(n); rep(i, n) cin >> m[i]; dual_segtree<F, compositon, id> seg(n); rep(_, q) { char c; int l, r, x; cin >> c >> l >> r >> x; l--; if (c == 'o') seg.apply(l, r, {~x, x}); else seg.apply(l, r, {~0, x}); } vector<mint> cnt(30, 1); rep(i, n) { auto [a, b] = seg.get(i); int x = b, y = a ^ b; mint f[2][30]; f[0][0] = 1; int k = m[i]; rep(_, 30) { mint g[2][2]; g[0][x & 1] = 1; g[1][y & 1] = 1; mint nf[4][30]; rep(i, 2) rep(j, 30) rep(p, 2) rep(q, 2) { nf[i+p][j+q] += f[i][j] * g[p][q]; } rrep(i, 3) rep(j, 30) nf[i+1][j] += nf[i][j]; rep(i, 4) if ((i & 1) == (k & 1)) rep(j, 30) { f[i >> 1][j] = nf[i][j]; } x >>= 1, y >>= 1, k >>= 1; } rep(j, 29) f[0][j+1] += f[0][j]; rep(j, 30) cnt[j] *= f[0][j]; } rrep(j, 29) cnt[j+1] -= cnt[j]; mint ans; rep(j, 30) ans += j * cnt[j]; cout << ans.val() << '\n'; }