結果
問題 |
No.3208 Parse AND OR Affection
|
ユーザー |
![]() |
提出日時 | 2025-07-18 16:07:56 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 5,000 ms |
コード長 | 4,193 bytes |
コンパイル時間 | 5,451 ms |
コンパイル使用メモリ | 335,240 KB |
実行使用メモリ | 28,040 KB |
最終ジャッジ日時 | 2025-07-18 16:08:05 |
合計ジャッジ時間 | 8,451 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using std::cerr; using std::cin; using std::cout; #if __has_include(<atcoder/all>) #include <atcoder/all> using mint = atcoder::modint998244353; istream &operator>>(istream &is, mint &a) { long long t; is >> t; a = t; return is; } ostream &operator<<(ostream &os, mint a) { return os << a.val(); } #endif typedef long double ld; #define long long long #define uint unsigned int #define ull unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(__i, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(__i, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define all(a) a.begin(), a.end() #define UNIQUE(a) \ sort(all(a)); \ a.erase(unique(all(a)), a.end()) #define sz(a) (int)a.size() #define vec vector #ifndef DEBUG #define cerr \ if (0) \ cerr // #undef assert // #define assert(...) void(0) #undef endl #define endl '\n' #endif template <typename T> ostream &operator<<(ostream &os, vector<T> a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template <typename T, size_t n> ostream &operator<<(ostream &os, array<T, n> a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template <typename T> istream &operator>>(istream &is, vector<T> &a) { for (T &i : a) is >> i; return is; } template <typename T, typename S> bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template <typename T, typename S> bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template <typename T> void operator++(vector<T> &a) { for (T &i : a) ++i; } template <typename T> void operator--(vector<T> &a) { for (T &i : a) --i; } template <typename T> void operator++(vector<T> &a, int) { for (T &i : a) i++; } template <typename T> void operator--(vector<T> &a, int) { for (T &i : a) i--; } struct S { long c0, c1; long x[4] = {}; int f, v; long ans; }; ostream &operator<<(ostream &os, S a) { return os << "c : " << a.c0 << " " << a.c1 << '\n' << "x : " << a.x[0] << " " << a.x[1] << " " << a.x[2] << " " << a.x[3] << '\n' << "f v : " << a.f << " " << a.v << '\n' << "ans : " << a.ans; } S e() { S res = S(); res.v = -1; return res; } int ap[4][4] = {{0, 0, 3, 3}, {0, 1, 2, 3}, {0, 2, 1, 3}, {0, 3, 0, 3}}; int fx[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}; S op(S l, S r) { if (r.v == -1) return l; if (l.v == -1) return r; long c0 = r.c0; long c1 = r.c1; (r.f == 0 || r.f == 1 ? c0 : c1) += l.c0; (r.f == 0 || r.f == 2 ? c0 : c1) += l.c1; long x[4] = {}; rep(k, 4) x[k] = l.x[k]; rep(k, 4) x[ap[l.f][k]] += r.x[k]; int f = ap[l.f][r.f]; int v = fx[r.f][l.v]; long ans = l.ans + r.ans + l.c0 * (r.x[2] + r.x[3]) + l.c1 * (r.x[1] + r.x[3]); S res = {c0, c1, {x[0], x[1], x[2], x[3]}, f, v, ans}; return res; } void solve() { int n, que; string s; cin >> n >> que >> s; s = "+" + s; n = (n + 1) / 2; vec<S> a(n); rep(i, n) { if (s[2 * i] == '+') { a[i].f = s[2 * i + 1] == 'T' ? 3 : 1; } else if (s[2 * i] == '*') { a[i].f = s[2 * i + 1] == 'T' ? 1 : 0; } else { a[i].f = s[2 * i + 1] == 'T' ? 2 : 1; } a[i].x[a[i].f]++; if (s[2 * i + 1] == 'T') { a[i].ans++; a[i].c1++; a[i].v = 1; } else a[i].c0++; } atcoder::segtree<S, op, e> seg(a); while (que--) { int l, r; cin >> l >> r; l--; l = (l + 1) / 2, r = (r + 1) / 2; S res = seg.prod(l, r); cout << res.ans << endl; } } int main() { // srand((unsigned)time(NULL)); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int t = 1; // cin >> t; while (t--) solve(); }