結果
問題 | No.2498 OX Operations |
ユーザー | kotatsugame |
提出日時 | 2023-10-06 23:37:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
19,296 KB |
testcase_01 | AC | 6 ms
19,368 KB |
testcase_02 | AC | 5 ms
20,112 KB |
testcase_03 | AC | 6 ms
19,236 KB |
testcase_04 | AC | 6 ms
19,468 KB |
testcase_05 | AC | 6 ms
20,304 KB |
testcase_06 | AC | 6 ms
20,804 KB |
testcase_07 | AC | 6 ms
19,428 KB |
testcase_08 | AC | 6 ms
19,620 KB |
testcase_09 | AC | 6 ms
19,528 KB |
testcase_10 | AC | 6 ms
19,808 KB |
testcase_11 | AC | 8 ms
19,388 KB |
testcase_12 | AC | 13 ms
19,600 KB |
testcase_13 | AC | 10 ms
19,404 KB |
testcase_14 | AC | 15 ms
19,940 KB |
testcase_15 | AC | 1,304 ms
51,016 KB |
testcase_16 | AC | 1,952 ms
51,236 KB |
testcase_17 | AC | 954 ms
51,092 KB |
testcase_18 | AC | 1,623 ms
51,408 KB |
testcase_19 | AC | 1,214 ms
51,492 KB |
testcase_20 | AC | 1,787 ms
51,460 KB |
testcase_21 | AC | 2,141 ms
51,556 KB |
testcase_22 | AC | 992 ms
27,696 KB |
testcase_23 | AC | 880 ms
27,324 KB |
testcase_24 | AC | 2,073 ms
51,448 KB |
testcase_25 | AC | 2,066 ms
51,268 KB |
testcase_26 | AC | 2,098 ms
51,384 KB |
ソースコード
#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; }