結果

問題 No.2762 Counting and Deleting
コンテスト
ユーザー 👑 tails
提出日時 2024-05-23 17:43:07
言語 C90(gcc15)
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -std=c90 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,241 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 91 ms
コンパイル使用メモリ 28,816 KB
最終ジャッジ日時 2026-02-24 01:19:49
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.c: In function 'main':
main.c:31:13: error: expected ';' before 'i'
   31 |         rep(i,n){
      |             ^
main.c:9:32: note: in definition of macro 'rep'
    9 | #define rep(v,e) for(typeof(e) v=0;v<e;++v)
      |                                ^
main.c:31:13: error: 'i' undeclared (first use in this function)
   31 |         rep(i,n){
      |             ^
main.c:9:36: note: in definition of macro 'rep'
    9 | #define rep(v,e) for(typeof(e) v=0;v<e;++v)
      |                                    ^
main.c:31:13: note: each undeclared identifier is reported only once for each function it appears in
   31 |         rep(i,n){
      |             ^
main.c:9:36: note: in definition of macro 'rep'
    9 | #define rep(v,e) for(typeof(e) v=0;v<e;++v)
      |                                    ^
main.c:43:15: error: expected ';' before 'i'
   43 |         rreps(i,1,1<<16){
      |               ^
main.c:10:36: note: in definition of macro 'rreps'
   10 | #define rreps(v,s,e) for(typeof(e) v=e;--v>=s;)
      |                                    ^
main.c:11:32: error: expected ';' before '_'
   11 | #define times(e) for(typeof(e) _=e;_--;)
      |                                ^
main.c:56:9: note: in expansion of macro 'times'
   56 |         times(q){
      |         ^~~~~
main.c:11:36: error: '_' undeclared (first use in this function)
   11 | #define times(e) for(typeof(e) _=e;_--;)
      |                                    ^
main.c:56:9: note: in expansion of macro 'times'
   56 |         times(q){
      |         ^~~~~
main.c:69:41: error: 'for' loop initial declarations are only allowed in C99 or C11 mode
   69 |                                         for(int i=l>>1;i;i>>=1){
      |                                         ^~~
main.c:69:41: note: use option '-std=c99', '-std=gnu99', '-std=c11' or '-std=gnu11' to compile your code

ソースコード

diff #
raw source code 

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