結果
問題 | No.2498 OX Operations |
ユーザー |
|
提出日時 | 2023-10-06 23:37:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,141 ms / 4,000 ms |
コード長 | 2,019 bytes |
コンパイル時間 | 950 ms |
コンパイル使用メモリ | 86,316 KB |
実行使用メモリ | 51,556 KB |
最終ジャッジ日時 | 2024-07-26 17:18:20 |
合計ジャッジ時間 | 21,407 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include<iostream>#include<cassert>#include<atcoder/modint>#include<atcoder/lazysegtree>using namespace std;using mint=atcoder::modint998244353;using dat=pair<bool,bool>;dat op(dat a,dat b){return a;}dat e(){return make_pair(false,false);}dat mp(int f,dat x){if(f==0);else if(f==1)x.first=!x.first,x.second=!x.second;else if(f==2)x=make_pair(false,false);else x=make_pair(true,true);return x;}int cmp(int f,int g){static const int tb[4][4]={{0,1,2,3},{1,0,3,2},{2,2,2,2},{3,3,3,3},};return tb[f][g];}int id(){return 0;}int N,Q;int M[1<<17];int F[1<<17],T[1<<17];mint dp[1<<17][31];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>Q;for(int i=0;i<N;i++)cin>>M[i];vector<dat>init(N,make_pair(false,true));atcoder::lazy_segtree<dat,op,e,int,mp,cmp,id>seg[30];for(int k=0;k<30;k++){seg[k]=atcoder::lazy_segtree<dat,op,e,int,mp,cmp,id>(init);}for(int i=0;i<Q;i++){char C;int L,R,X;cin>>C>>L>>R>>X;L--;if(C=='o'){for(int k=0;k<30;k++)if(X>>k&1){seg[k].apply(L,R,3);}}else{for(int k=0;k<30;k++)if(X>>k&1){seg[k].apply(L,R,1);}}}for(int k=0;k<30;k++){for(int i=0;i<N;i++){dat t=seg[k].get(i);if(t.first)F[i]|=1<<k;if(t.second)T[i]|=1<<k;}}dp[0][0]=1;for(int i=0;i<N;i++){mint way[2][2][31];int now=0;for(int a=0;a<2;a++)for(int b=0;b<=30;b++)way[now][a][b]=0;way[now][0][0]=1;for(int k=30;k--;){int nxt=1-now;for(int a=0;a<2;a++)for(int b=0;b<=30;b++)way[nxt][a][b]=0;for(int j=0;j<2;j++){int up=j?1:M[i]>>k&1;for(int b=0;b<=up;b++){int p=(b?T[i]:F[i])>>k&1;for(int l=0;l<30;l++){way[nxt][j|b<up][l+p]+=way[now][j][l];}}}now=nxt;}for(int a=0;a<=30;a++)for(int b=0;b<=30;b++){dp[i+1][max(a,b)]+=dp[i][a]*(way[now][0][b]+way[now][1][b]);}}mint ans=0;for(int k=0;k<=30;k++)ans+=mint::raw(k)*dp[N][k];cout<<ans.val()<<endl;}