結果
問題 |
No.3208 Parse AND OR Affection
|
ユーザー |
|
提出日時 | 2025-07-20 12:20:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,288 bytes |
コンパイル時間 | 5,023 ms |
コンパイル使用メモリ | 295,812 KB |
実行使用メモリ | 33,208 KB |
最終ジャッジ日時 | 2025-07-20 12:20:23 |
合計ジャッジ時間 | 11,451 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | WA * 20 |
ソースコード
#line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.hpp> #else template <class T> concept Streamable = requires(ostream os, T &x) { os << x; }; template <class mint> concept is_modint = requires(mint &x) { { x.val() } -> std::convertible_to<int>; }; #define debug(...) #endif template <Streamable T> void print_one(const T &value) { cout << value; } template <is_modint T> void print_one(const T &value) { cout << value.val(); } void print() { cout << '\n'; } template <class T, class... Ts> void print(const T &a, const Ts &...b) { print_one(a); ((cout << ' ', print_one(b)), ...); cout << '\n'; } template <ranges::range Iterable> requires(!Streamable<Iterable>) void print(const Iterable &v) { for(auto it = v.begin(); it != v.end(); ++it) { if(it != v.begin()) cout << " "; print_one(*it); } cout << '\n'; } using vi = vector<int>; using vii = vector<vector<int>>; using pii = pair<int, int>; using ll = long long; using vl = vector<ll>; using vll = vector<vl>; using pll = pair<ll, ll>; #define all(v) begin(v), end(v) template <class T> void UNIQUE(T &v) { ranges::sort(v); v.erase(unique(all(v)), end(v)); } template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } // https://trap.jp/post/1224/ template <class... T> constexpr auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } template <class... T> constexpr auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class... T> void input(T &...a) { (cin >> ... >> a); } template <class T> void input(vector<T> &a) { for(T &x : a) cin >> x; } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1_0(n, c) REP1_1(n, c) #define REP1_1(n, c) \ for(ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(n); REP_COUNTER_##c++) #define REP1(n) REP1_0(n, __COUNTER__) #define REP2(i, a) for(ll i = 0; i < (ll)(a); i++) #define REP3(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++) #define REP4(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c)) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; template <class T> constexpr T floor(T x, T y) noexcept { return x / y - ((x ^ y) < 0 and x % y); } template <class T> constexpr T ceil(T x, T y) noexcept { return x / y + ((x ^ y) >= 0 and x % y); } // yの符号に関わらず非負で定義 \bmod:texコマンド template <class T> constexpr T bmod(T x, T y) noexcept { T m = x % y; return (m < 0) ? m + (y > 0 ? y : -y) : m; } template <std::signed_integral T> constexpr int bit_width(T x) noexcept { return std::bit_width((uint64_t)x); } template <std::signed_integral T> constexpr int popcount(T x) noexcept { return std::popcount((uint64_t)x); } constexpr bool kth_bit(auto n, auto k) { return (n >> k) & 1; } #line 3 "data-structure/lazy-segtree.hpp" // template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), // F (*composition)(F, F), F (*id)()> template <class S, auto op, S (*e)(), class F, auto mapping, auto composition, auto id> // composition(f,g)(x) = f∘g(x) = f(g(x)) // aclと同じ、maspyさん記事と逆 struct lazy_segtree { int n; vector<S> v; vector<F> vf; explicit lazy_segtree(int n) : n(n), v(vector<S>(2 * n, e())), vf(vector<F>(2 * n, id())) {}; explicit lazy_segtree(const vector<S> &v_) : n(v_.size()), v(2 * n, e()), vf(2 * n, id()) { for(int i = 0; i < n; ++i) v[i + n] = v_[i]; for(int i = n - 1; i > 0; --i) v[i] = op(v[i << 1], v[i << 1 | 1]); } void apply(int l, int r, F f) { l += n; r += n; int l0 = l / (l & -l); int r0 = r / (r & -r) - 1; propagate_above(l0); propagate_above(r0); while(l < r) { if(l & 1) { apply_at(l, f); l++; } if(r & 1) { r--; apply_at(r, f); } l >>= 1; r >>= 1; } recul_above(l0); recul_above(r0); } S get(int x) { x += n; int maxi = (int)bit_width((unsigned)x) - 1; for(int i = maxi; i > 0; --i) propagate_at(x >> i); return v[x]; } void set(int x, S s) { x += n; propagate_above(x); v[x] = s; recul_above(x); } S prod(int l, int r) { l += n; r += n; int l0 = l / (l & -l); int r0 = r / (r & -r) - 1; propagate_above(l0); propagate_above(r0); S sl = e(), sr = e(); while(l < r) { if(l & 1) { sl = op(sl, v[l]); l++; } if(r & 1) { r--; sr = op(v[r], sr); } l >>= 1; r >>= 1; } return op(sl, sr); } S all_prod_commute() { // 可換なモノイド専用 // 2冪にすれば非可換でも良さそう return v[1]; } private: void apply_at(int x, F f) { v[x] = mapping(f, v[x]); if(x < n) vf[x] = composition(f, vf[x]); } void propagate_at(int x) { apply_at(x << 1, vf[x]); apply_at(x << 1 | 1, vf[x]); vf[x] = id(); } void propagate_above(int x) { int maxi = (int)bit_width((unsigned)x) - 1; for(int i = maxi; i > 0; --i) { propagate_at(x >> i); } return; } void recul_above(int x) { while(x > 1) { x >>= 1; v[x] = op(v[x << 1], v[x << 1 | 1]); } } }; #line 3 "math/matrix.hpp" template <class T> struct Matrix { int height, width; vector<T> A; Matrix() = default; Matrix(int n, int m) : height(n), width(m), A(n * m, T(0)) {} Matrix(int n) : Matrix(n, n) {} Matrix(vector<vector<T>> A_) : height(A_.size()), width(A_[0].size()) { A.reserve(height * width); for(auto &&row : A_ | views::join) A.emplace_back(row); } inline const T &operator()(int i, int j) const { return A[i * width + j]; } inline T &operator()(int i, int j) { return A[i * width + j]; } void show() const { for(int i = 0; i < height; ++i) { for(int j = 0; j < width; ++j) { if constexpr(is_arithmetic_v<T>) { cout << (*this)(i, j) << " \n"[j + 1 == width]; } else { // atcoder::modint用 cout << (*this)(i, j).val() << " \n"[j + 1 == width]; } } } } Matrix &operator+=(const Matrix &B) { assert(height == B.height && width == B.width); for(int i = 0; i < height * width; ++i) A[i] += B.A[i]; return *this; } Matrix &operator-=(const Matrix &B) { assert(height == B.height && width == B.width); for(int i = 0; i < height * width; ++i) A[i] -= B.A[i]; return *this; } Matrix &operator*=(const Matrix &B) { assert(width == B.height); // (height,width)*(B.height,B.width) -> (height,B.width) Matrix<T> res(height, B.width); for(int i = 0; i < height; ++i) { for(int k = 0; k < width; ++k) { for(int j = 0; j < B.width; ++j) { res(i, j) += (*this)(i, k) * B(k, j); } } } swap(*this, res); return *this; } Matrix &operator^=(size_t k) { assert(height == width); Matrix<T> res(height); for(int i = 0; i < height; ++i) res(i, i) = T(1); while(k) { if(k & 1) { res *= (*this); } (*this) *= (*this); k >>= 1; } swap(res, *this); return *this; } [[nodiscard]] Matrix pow(size_t k) const { auto res(*this); res ^= k; return res; } [[nodiscard]] Matrix operator+(const Matrix &B) const { return Matrix(*this) += B; } [[nodiscard]] Matrix operator-(const Matrix &B) const { return Matrix(*this) -= B; } [[nodiscard]] Matrix operator*(const Matrix &B) const { return Matrix(*this) *= B; } }; #line 4 "/home/y_midori/cp/test.cpp" struct S { ll t{}, f{}, rt{}, rf{}; }; S op(S a, S b) { return S(a.t + b.t, a.f + b.f, a.rt + b.rt, a.rf + b.rf); } S e() { return S(); } struct F { // A = [[a00,a01],[a10,a11]], B = [[b00,b01],[b10,b11]] ll a00, a01, a10, a11; ll b00, b01, b10, b11; }; S mapping(const F &f, const S &s) { S res; // new rt, rf res.rt = f.a00 * s.rt + f.a01 * s.rf; res.rf = f.a10 * s.rt + f.a11 * s.rf; // new t, f res.t = s.t + f.b00 * s.rt + f.b01 * s.rf; res.f = s.f + f.b10 * s.rt + f.b11 * s.rf; return res; } F cmp(const F &f, const F &g) { // 作用素合成: h = g ∘ f F h; // h.A = g.A * f.A h.a00 = g.a00 * f.a00 + g.a01 * f.a10; h.a01 = g.a00 * f.a01 + g.a01 * f.a11; h.a10 = g.a10 * f.a00 + g.a11 * f.a10; h.a11 = g.a10 * f.a01 + g.a11 * f.a11; // h.B = g.B * f.A + f.B h.b00 = g.b00 * f.a00 + g.b01 * f.a10 + f.b00; h.b01 = g.b00 * f.a01 + g.b01 * f.a11 + f.b01; h.b10 = g.b10 * f.a00 + g.b11 * f.a10 + f.b10; h.b11 = g.b10 * f.a01 + g.b11 * f.a11 + f.b11; return h; } F id() { return F{1, 0, 0, 1, 0, 0, 0, 0}; } static const F OP_F = {0, 0, 1, 1, 0, 0, 1, 1}; static const F OP_plusT = {1, 1, 0, 0, 1, 1, 0, 0}; static const F OP_xorT = {0, 1, 1, 0, 0, 1, 1, 0}; static const F OP_id = {1, 0, 0, 1, 1, 0, 0, 1}; void solve() { INT(n, q); STR(s); n = ceil(n, 2); vi l(q), r(q), ord(q); rep(i, q) { input(l[i], r[i]); l[i] /= 2; r[i] = ceil(r[i], 2); ord[i] = i; } ranges::sort(ord, {}, [&](int i) { return r[i]; }); vl ans(q); lazy_segtree<S, op, e, F, mapping, cmp, id> seg([&] { vector<S> v(n); rep(i, n) { bool flag = s[2 * i] == 'T'; v[i] = S(flag, !flag, flag, !flag); } return v; }()); int cur_r = 1; for(auto i : ord) { while(r[i] > cur_r) { char c1 = s[2 * cur_r - 1]; char c2 = s[2 * cur_r]; const F *opF = &OP_id; if(c1 == '*' && c2 == 'F') { opF = &OP_F; } else if(c1 == '+' && c2 == 'T') { opF = &OP_plusT; } else if(c1 == '^' && c2 == 'T') { opF = &OP_xorT; } // [0, cur_r) の範囲に一括で適用 seg.apply(0, cur_r, *opF); cur_r++; } ans[i] = seg.prod(l[i], r[i]).t; // #ifdef LOCAL // debug(i, l[i], r[i], cur_r); // rep(j, n) cout << seg.get(j).t << " \n"[j + 1 == n]; // rep(j, n) cout << seg.get(j).f << " \n"[j + 1 == n]; // rep(j, n) cout << seg.get(j).rt << " \n"[j + 1 == n]; // rep(j, n) cout << seg.get(j).rf << " \n"[j + 1 == n]; // #endif } rep(i, q) { print(ans[i]); } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int t = 1; rep(t) solve(); }