結果
問題 | No.2992 Range ABCD String Query |
ユーザー |
|
提出日時 | 2024-12-16 19:10:56 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 551 ms / 6,000 ms |
コード長 | 1,979 bytes |
コンパイル時間 | 3,908 ms |
コンパイル使用メモリ | 252,008 KB |
実行使用メモリ | 32,000 KB |
最終ジャッジ日時 | 2024-12-16 23:49:43 |
合計ジャッジ時間 | 19,116 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/segtree>using namespace std;using namespace atcoder;using ll = long long;const int inf = 1e6;struct S {int AA, AB, AC, AD, BB, BC, BD, CC, CD, DD;};S op(S l, S r) {S rt;rt.AA = l.AA + r.AA;rt.AB = min({l.AA + r.AB, l.AA + r.BB, l.AB + r.BB});rt.AC = min({l.AA + r.AC, l.AA + r.BC, l.AA + r.CC, l.AB + r.BC, l.AB + r.CC, l.AC + r.CC});rt.AD = min({l.AA + r.AD, l.AA + r.BD, l.AA + r.CD, l.AA + r.DD, l.AB + r.BD, l.AB + r.CD, l.AB + r.DD, l.AC + r.CD, l.AC + r.DD, l.AD + r.DD});rt.BB = l.BB + r.BB;rt.BC = min({l.BB + r.BC, l.BB + r.CC, l.BC + r.CC});rt.BD = min({l.BB + r.BD, l.BB + r.CD, l.BB + r.DD, l.BC + r.CD, l.BC + r.DD, l.BD + r.DD});rt.CC = l.CC + r.CC;rt.CD = min({l.CC + r.CD, l.CC + r.DD, l.CD + r.DD});rt.DD = l.DD + r.DD;return rt;}S e() {return S{0, 0, 0, 0, 0, 0, 0, 0, 0, 0};}int main() {int N, Q;cin >> N >> Q;string S_;cin >> S_;vector<S> v(N);for (int i = 0; i < N; i++) {if (S_[i] == 'A') {v[i] = S{0, inf, inf, inf, 1, inf, inf, 1, inf, 1};}if (S_[i] == 'B') {v[i] = S{1, inf, inf, inf, 0, inf, inf, 1, inf, 1};}if (S_[i] == 'C') {v[i] = S{1, inf, inf, inf, 1, inf, inf, 0, inf, 1};}if (S_[i] == 'D') {v[i] = S{1, inf, inf, inf, 1, inf, inf, 1, inf, 0};}}segtree<S, op, e> seg(v);for (int i = 0; i < Q; i++) {int t;cin >> t;if (t == 1) {int x;char c;cin >> x >> c;x--;if (c == 'A') {seg.set(x, S{0, inf, inf, inf, 1, inf, inf, 1, inf, 1});}if (c == 'B') {seg.set(x, S{1, inf, inf, inf, 0, inf, inf, 1, inf, 1});}if (c == 'C') {seg.set(x, S{1, inf, inf, inf, 1, inf, inf, 0, inf, 1});}if (c == 'D') {seg.set(x, S{1, inf, inf, inf, 1, inf, inf, 1, inf, 0});}} else {int l, r;cin >> l >> r;l--; r--;S s = seg.prod(l, r + 1);cout << min({s.AA, s.AB, s.AC, s.AD, s.BB, s.BC, s.BD, s.CC, s.CD, s.DD}) << '\n';}}}