結果

問題 No.2762 Counting and Deleting
ユーザー tailstails
提出日時 2024-05-23 18:02:09
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 25 ms / 4,000 ms
コード長 4,534 bytes
コンパイル時間 677 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-12-20 18:56:08
合計ジャッジ時間 1,663 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 12 ms
5,888 KB
testcase_08 AC 12 ms
5,888 KB
testcase_09 AC 12 ms
5,888 KB
testcase_10 AC 12 ms
6,016 KB
testcase_11 AC 23 ms
6,016 KB
testcase_12 AC 23 ms
6,016 KB
testcase_13 AC 22 ms
6,144 KB
testcase_14 AC 23 ms
6,016 KB
testcase_15 AC 25 ms
6,400 KB
testcase_16 AC 25 ms
6,400 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:172:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
  172 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:173:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  173 |         _exit(0);
      |         ^~~~~
main.c:173:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

diff # 

#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 998244353

typedef unsigned long ulong;

char wbuf[1<<25];

typedef struct{
	unsigned m00,m01,m02;
	unsigned m10,m11,m12;
	int skip;
	int dirty;
}N;

N tree[1<<17];
int qs[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;
					for(int i=l>>1;i;i>>=1){
						N*np=&tree[i];
						np->dirty=1;
					}
					l+=1;
				}
			}
		}
		if(t=='2'){
			unsigned f=0;
			unsigned v0=0;
			unsigned v1=0;
			while(l<r){
				if(l&1){
					N*np=&tree[l];
					int qn=0;
					qs[qn++]=l;
					while(qn){
						int i=qs[--qn];
						N*np=&tree[i];
						N*c0=&tree[i*2+0];
						N*c1=&tree[i*2+1];
						if(np->dirty){
							if(!c0->dirty&&!c1->dirty){
								if(c0->skip){
									*np=*c1;
								}else if(c1->skip){
									*np=*c0;
								}else{
									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;
									np->dirty=0;
								}
							}else{
								qs[qn++]=i;
								qs[qn++]=i*2+1;
								qs[qn++]=i*2+0;
							}
						}
					}
					if(!np->skip){
						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){
				r=r<<1|f&1;
				f>>=1;
				if(r&1){
					N*np=&tree[r-1];
					int qn=0;
					qs[qn++]=l;
					while(qn){
						int i=qs[--qn];
						N*np=&tree[i];
						N*c0=&tree[i*2+0];
						N*c1=&tree[i*2+1];
						if(np->dirty){
							if(!c0->dirty&&!c1->dirty){
								if(c0->skip){
									*np=*c1;
								}else if(c1->skip){
									*np=*c0;
								}else{
									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;
									np->dirty=0;
								}
							}else{
								qs[qn++]=i;
								qs[qn++]=i*2+1;
								qs[qn++]=i*2+0;
							}
						}
					}
					if(!np->skip){
						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);
}
0