結果
問題 |
No.2992 Range ABCD String Query
|
ユーザー |
|
提出日時 | 2024-12-17 00:36:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 641 ms / 6,000 ms |
コード長 | 1,360 bytes |
コンパイル時間 | 6,283 ms |
コンパイル使用メモリ | 313,228 KB |
実行使用メモリ | 48,988 KB |
最終ジャッジ日時 | 2024-12-17 00:37:08 |
合計ジャッジ時間 | 26,081 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using mint = atcoder::static_modint<998244353>; //using mint = atcoder::static_modint<1000000007>; using namespace std; using namespace atcoder; using ld = long double; using ll = long long; #define mp(a,b) make_pair(a,b) #define rep(i,s,n) for(int i=s; i<n; i++) const vector<int> dx{1,0,-1,0},dy{0,1,0,-1}; struct P{ int a[4][4]; P(){ rep(i,0,4)rep(j,0,4)a[i][j]=0; } }; P convert(char c){ P z; rep(i,0,4)rep(j,i,4){ if(i<=c-'A' && c-'A'<=j)z.a[i][j]=0; else z.a[i][j]=1; } return z; } P op(P x,P y){ P z; rep(i,0,4)rep(j,i,4)z.a[i][j]=1e9; rep(i,0,4)rep(j,i,4)rep(k,j,4){ z.a[i][k]=min(z.a[i][k],x.a[i][j]+y.a[j][k]); } return z; } P e(){return P();} int main(){ int n,Q; cin >> n >> Q; string s; cin >> s; segtree<P,op,e> seg(n); rep(i,0,n)seg.set(i,convert(s[i])); vector<int> out; rep(q,0,Q){ int t;cin >> t; if(t==1){ int x;cin >> x; char c;cin >> c; seg.set(x-1,convert(c)); continue; } int l,r; cin >> l >> r; l--; auto p=seg.prod(l,r); int ans=1e9; rep(i,0,4)rep(j,i,4)ans=min(ans,p.a[i][j]); out.push_back(ans); } for(auto x:out)cout << x << "\n"; }