結果
問題 |
No.3208 Parse AND OR Affection
|
ユーザー |
|
提出日時 | 2025-07-25 13:35:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,872 bytes |
コンパイル時間 | 2,857 ms |
コンパイル使用メモリ | 219,900 KB |
実行使用メモリ | 12,840 KB |
最終ジャッジ日時 | 2025-07-25 13:35:22 |
合計ジャッジ時間 | 7,352 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | WA * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include "debug.h" #else #define dbg(...) 0 #define dbgn(...) 0 #endif const int ID = 0, NOT = 1, SET_T = 2, SET_F = 3; int n, q, m, block_size; vector<int> v, t; vector<int> pref_not; vector<int> prev_stable, next_stable, next_stable_type; vector<int> val_q_stable; vector<vector<vector<int>>> count_v_par; vector<vector<int>> count_pnp; ll a_query(int q, int l) { if (l > q) { return 0; } ll ans = 0; int k_s = prev_stable[q]; int p_end1 = min(q, k_s); if (l <= p_end1) { if (val_q_stable[q] == 1) { ans += (ll)p_end1 - l + 1; } } int p_start2 = max(l, k_s + 1); if (p_start2 <= q) { int par_q_minus_1 = (q > 1) ? (pref_not[q - 1] % 2) : 0; int target_par_T = par_q_minus_1; ans += count_v_par[1][target_par_T][q] - count_v_par[1][target_par_T][p_start2 - 1]; int target_par_F = (par_q_minus_1 - 1 + 2) % 2; ans += count_v_par[0][target_par_F][q] - count_v_par[0][target_par_F][p_start2 - 1]; } return ans; } ll count_t(int p, int l, int r) { if (l > r) { return 0; } ll ans = 0; if (l <= p && p <= r && v[p] == 1) { ans += 1; } int q_range_start = max(l, p + 1); if (q_range_start > r) { return ans; } int k_s = next_stable[p]; int q_end1 = min(r, k_s); if (q_range_start <= q_end1) { int par_p_minus_1 = (p > 1) ? (pref_not[p - 1] % 2) : 0; int target_par = (1 - v[p] + par_p_minus_1) % 2; ans += count_pnp[target_par][q_end1] - count_pnp[target_par][q_range_start - 1]; } int q_start2 = max(q_range_start, k_s + 1); if (q_start2 <= r) { int stable_val = next_stable_type[p]; int par_at_k_s = (k_s > 0) ? (pref_not[k_s] % 2) : 0; int target_par = (1 - stable_val + par_at_k_s) % 2; ans += count_pnp[target_par][r] - count_pnp[target_par][q_start2 - 1]; } return ans; } void pre(const string& x) { m = (n + 1) / 2; block_size = sqrt(m); if (block_size == 0) { block_size = 1; } v.resize(m + 1); t.resize(m + 1); pref_not.resize(m + 1, 0); for (int p = 1; p <= m; ++p) { v[p] = (x[2 * p - 2] == 'T'); } for (int k = 1; k < m; ++k) { char op = x[2 * k - 1]; int val_next = (x[2 * k] == 'T'); if (op == '+') { t[k] = val_next ? SET_T : ID; } else if (op == '*') { t[k] = val_next ? ID : SET_F; } else { t[k] = val_next ? NOT : ID; } } for (int k = 1; k < m; ++k) { pref_not[k] = pref_not[k - 1] + (t[k] == NOT); } prev_stable.resize(m + 2, 0); int last_or_t = 0, last_and_f = 0; for (int i = 1; i <= m; ++i) { if (i > 1) { if (t[i - 1] == SET_T) last_or_t = i - 1; if (t[i - 1] == SET_F) last_and_f = i - 1; } prev_stable[i] = max(last_or_t, last_and_f); } next_stable.resize(m + 1, m + 1); next_stable_type.resize(m + 1, 0); int next_or_t = m + 1, next_and_f = m + 1; for (int p = m - 1; p >= 1; --p) { if (t[p] == SET_T) next_or_t = p; if (t[p] == SET_F) next_and_f = p; if (next_or_t < next_and_f) { next_stable[p] = next_or_t; next_stable_type[p] = 1; } else { next_stable[p] = next_and_f; next_stable_type[p] = 0; } } val_q_stable.resize(m + 1, 0); for (int i = 1; i <= m; ++i) { int k_s = prev_stable[i]; if (k_s > 0) { int val_at_stable = (t[k_s] == SET_T); int nots_after = pref_not[i - 1] - pref_not[k_s - 1]; val_q_stable[i] = val_at_stable ^ (nots_after % 2); } } count_v_par.assign(2, vector<vector<int>>(2, vector<int>(m + 1, 0))); for (int p = 1; p <= m; ++p) { for (int val = 0; val < 2; ++val) { for (int par = 0; par < 2; ++par) { count_v_par[val][par][p] = count_v_par[val][par][p - 1]; } } int par_p_minus_1 = (p > 1) ? (pref_not[p - 1] % 2) : 0; count_v_par[v[p]][par_p_minus_1][p]++; } count_pnp.assign(2, vector<int>(m + 1, 0)); for (int i = 1; i <= m; ++i) { count_pnp[0][i] = count_pnp[0][i - 1]; count_pnp[1][i] = count_pnp[1][i - 1]; int par_i_minus_1 = (i > 1) ? (pref_not[i - 1] % 2) : 0; count_pnp[par_i_minus_1][i]++; } } struct QUERY { int l, r, og_idx, bl; bool operator<(const QUERY& other) const { if (bl != other.bl) { return bl < other.bl; } return (bl % 2) ? (r < other.r) : (r > other.r); } }; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> q; string x; cin >> x; pre(x); vector<QUERY> queries(q); for (int i = 0; i < q; i++) { int l_in, r_in; cin >> l_in >> r_in; queries[i].l = (l_in + 1) / 2; queries[i].r = (r_in + 1) / 2; queries[i].og_idx = i; queries[i].bl = queries[i].l / block_size; } sort(queries.begin(), queries.end()); vector<ll> ans(q); int cl = 1, cr = 0; ll cur_ans = 0; for (const auto& Q : queries) { while (cl > Q.l) { cl--; cur_ans += count_t(cl, cl, cr); } while (cr < Q.r) { cr++; cur_ans += a_query(cr, cl); } while (cl < Q.l) { cur_ans -= count_t(cl, cl, cr); cl++; } while (cr > Q.r) { cur_ans -= a_query(cr, cl); cr--; } ans[Q.og_idx] = cur_ans; } for (int i = 0; i < q; i++) { cout << ans[i] << '\n'; } return 0; }