結果
| 問題 | No.2762 Counting and Deleting |
| ユーザー |
 tails
|
| 提出日時 | 2024-05-23 17:41:33 |
| 言語 | C90 (gcc 12.3.0) |
| 結果 |
AC
|
| 実行時間 | 26 ms / 4,000 ms |
| コード長 | 3,188 bytes |
| コンパイル時間 | 613 ms |
| コンパイル使用メモリ | 28,928 KB |
| 実行使用メモリ | 6,016 KB |
| 最終ジャッジ日時 | 2024-12-20 18:55:12 |
| 合計ジャッジ時間 | 1,935 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 |
コンパイルメッセージ
main.c: In function ‘main’:
main.c:120:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
120 | write(1,wbuf,wp-wbuf);
| ^~~~~
main.c:121:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
121 | _exit(0);
| ^~~~~
main.c:121:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC target("avx2")#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})#define WTHI(v) {unsigned _z=v,_n=0;long _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;}#define WTLO(v) {unsigned _z=v,_n=8;long _d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;}#define wt(v) if(v>=100000000){WTLO(v/10);*wp++=v%10+'0';}else{WTHI(v);}#define rep(v,e) for(typeof(e) v=0;v<e;++v)#define rreps(v,s,e) for(typeof(e) v=e;--v>=s;)#define times(e) for(typeof(e) _=e;_--;)#define chmax(v,a) (v=v>=a?v:a)#define MD 998244353typedef unsigned long ulong;char wbuf[1<<25];typedef struct{unsigned m00,m01,m02;unsigned m10,m11,m12;int skip;}N;N tree[1<<17];int main(){rd_init();int n=rd();int q=rd();rep(i,n){N*np=&tree[1<<16|i];np->m00=1;np->m11=1;int c=*rp++;if(c=='0'){np->m01=1;}else{np->m10=1;np->m12=1;}}rreps(i,1,1<<16){N*np=&tree[i];N*c0=&tree[i*2+0];N*c1=&tree[i*2+1];np->m00=((ulong)c1->m00*(ulong)c0->m00+(ulong)c1->m01*(ulong)c0->m10)%MD;np->m01=((ulong)c1->m00*(ulong)c0->m01+(ulong)c1->m01*(ulong)c0->m11)%MD;np->m02=((ulong)c1->m00*(ulong)c0->m02+(ulong)c1->m01*(ulong)c0->m12+c1->m02)%MD;np->m10=((ulong)c1->m10*(ulong)c0->m00+(ulong)c1->m11*(ulong)c0->m10)%MD;np->m11=((ulong)c1->m10*(ulong)c0->m01+(ulong)c1->m11*(ulong)c0->m11)%MD;np->m12=((ulong)c1->m10*(ulong)c0->m02+(ulong)c1->m11*(ulong)c0->m12+c1->m12)%MD;}++rp;char*wp=wbuf;times(q){int t=*rp;rp+=2;int l=1<<16|rd()-1;int r=1<<16|rd();if(t=='1'){while(l<r){int x=tree[l].skip;if(x){chmax(tree[l].skip,r);l=x;}else{tree[l].skip=r;{N*np=&tree[l];np->m00=1; np->m01=0; np->m02=0;np->m10=0; np->m11=1; np->m12=0;}for(int i=l>>1;i;i>>=1){N*np=&tree[i];N*c0=&tree[i*2+0];N*c1=&tree[i*2+1];np->m00=((ulong)c1->m00*(ulong)c0->m00+(ulong)c1->m01*(ulong)c0->m10)%MD;np->m01=((ulong)c1->m00*(ulong)c0->m01+(ulong)c1->m01*(ulong)c0->m11)%MD;np->m02=((ulong)c1->m00*(ulong)c0->m02+(ulong)c1->m01*(ulong)c0->m12+c1->m02)%MD;np->m10=((ulong)c1->m10*(ulong)c0->m00+(ulong)c1->m11*(ulong)c0->m10)%MD;np->m11=((ulong)c1->m10*(ulong)c0->m01+(ulong)c1->m11*(ulong)c0->m11)%MD;np->m12=((ulong)c1->m10*(ulong)c0->m02+(ulong)c1->m11*(ulong)c0->m12+c1->m12)%MD;}l+=1;}}}if(t=='2'){unsigned f=1;unsigned v0=0;unsigned v1=0;while(l<r){if(l&1){N*np=&tree[l];unsigned u0=((ulong)np->m00*v0+(ulong)np->m01*v1+np->m02)%MD;unsigned u1=((ulong)np->m10*v0+(ulong)np->m11*v1+np->m12)%MD;v0=u0;v1=u1;}l=l+1>>1;f=f<<1|r&1;r>>=1;}while(f>1){r=r<<1|f&1;f>>=1;if(r&1){N*np=&tree[r-1];unsigned u0=((ulong)np->m00*v0+(ulong)np->m01*v1+np->m02)%MD;unsigned u1=((ulong)np->m10*v0+(ulong)np->m11*v1+np->m12)%MD;v0=u0;v1=u1;}}wt((v0+v1)%MD);*wp++='\n';}}write(1,wbuf,wp-wbuf);_exit(0);}