#983331 (C90) No.2762 Counting and Deleting

• 問題: No.2762 Counting and Deleting
• ユーザー: tails
• 提出日時: 2024-05-23 18:02:09
• 言語: C90 (gcc 11.4.0)
• 結果: AC
• 実行時間: 19 ms / 4,000 ms
• コード長: 4,534 bytes
• コンパイル時間: 907 ms
• コンパイル使用メモリ: 30,592 KB
• 実行使用メモリ: 7,516 KB
• 最終ジャッジ日時: 2024-05-23 18:02:12
• 合計ジャッジ時間: 1,844 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	9 ms; 6,940 KB
testcase_08	AC	10 ms; 7,384 KB
testcase_09	AC	10 ms; 6,944 KB
testcase_10	AC	9 ms; 7,132 KB
testcase_11	AC	19 ms; 7,128 KB
testcase_12	AC	18 ms; 7,512 KB
testcase_13	AC	18 ms; 7,260 KB
testcase_14	AC	19 ms; 6,944 KB
testcase_15	AC	19 ms; 6,944 KB
testcase_16	AC	18 ms; 7,516 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]

ソースコード

#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);
}