結果
問題 | No.2498 OX Operations |
ユーザー | kotatsugame |
提出日時 | 2023-10-06 23:31:34 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,039 bytes |
コンパイル時間 | 1,086 ms |
コンパイル使用メモリ | 89,280 KB |
実行使用メモリ | 60,048 KB |
最終ジャッジ日時 | 2024-07-26 17:17:14 |
合計ジャッジ時間 | 10,887 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
26,496 KB |
testcase_01 | AC | 7 ms
19,324 KB |
testcase_02 | AC | 7 ms
19,408 KB |
testcase_03 | AC | 7 ms
20,176 KB |
testcase_04 | AC | 7 ms
19,916 KB |
testcase_05 | AC | 7 ms
19,548 KB |
testcase_06 | AC | 7 ms
19,224 KB |
testcase_07 | AC | 7 ms
19,564 KB |
testcase_08 | AC | 7 ms
19,876 KB |
testcase_09 | AC | 6 ms
19,280 KB |
testcase_10 | AC | 7 ms
19,480 KB |
testcase_11 | AC | 10 ms
19,368 KB |
testcase_12 | AC | 20 ms
19,660 KB |
testcase_13 | AC | 19 ms
20,416 KB |
testcase_14 | AC | 27 ms
19,580 KB |
testcase_15 | AC | 3,408 ms
52,776 KB |
testcase_16 | TLE | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
ソースコード
#include<iostream> #include<cassert> #include<atcoder/modint> #include<atcoder/lazysegtree> using namespace std; using mint=atcoder::modint998244353; bool op(bool a,bool b){return a;} bool e(){return false;} bool mp(int f,bool x) { if(f==0); else if(f==1)x=!x; else if(f==2)x=false; else x=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<bool>initF(N,false),initT(N,true); atcoder::lazy_segtree<bool,op,e,int,mp,cmp,id>segF[30],segT[30]; for(int k=0;k<30;k++) { segF[k]=atcoder::lazy_segtree<bool,op,e,int,mp,cmp,id>(initF); segT[k]=atcoder::lazy_segtree<bool,op,e,int,mp,cmp,id>(initT); } 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) { segF[k].apply(L,R,3); segT[k].apply(L,R,3); } } else { for(int k=0;k<30;k++)if(X>>k&1) { segF[k].apply(L,R,1); segT[k].apply(L,R,1); } } } for(int k=0;k<30;k++) { for(int i=0;i<N;i++) { if(segF[k].get(i))F[i]|=1<<k; if(segT[k].get(i))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; }