結果

問題 No.619 CardShuffle
ユーザー tailstails
提出日時 2017-12-19 03:54:03
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 5,068 bytes
コンパイル時間 647 ms
コンパイル使用メモリ 31,808 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-24 14:16:15
合計ジャッジ時間 6,639 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 WA -
testcase_02 AC 0 ms
4,380 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:15:1: 警告: データ定義が型または記憶域クラスを持っていません
   15 | ops[101010];
      | ^~~
main.c:15:1: 警告: 型がデフォルトの ‘int’ に ‘ops’ の宣言内でなります [-Wimplicit-int]
main.c:114:1: 警告: 戻り値の型をデフォルトの ‘int’ にします [-Wimplicit-int]
  114 | mtoa(j,i){
      | ^~~~
main.c: 関数 ‘mtoa’ 内:
main.c:114:1: 警告: ‘j’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:114:1: 警告: ‘i’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c: トップレベル:
main.c:155:1: 警告: 戻り値の型をデフォルトの ‘int’ にします [-Wimplicit-int]
  155 | atom_i(i){
      | ^~~~~~
main.c: 関数 ‘atom_i’ 内:
main.c:155:1: 警告: ‘i’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c: トップレベル:
main.c:215:1: 警告: 戻り値の型をデフォルトの ‘int’ にします [-Wimplicit-int]
  215 | main(n,q,i,c,d,t,x,y){
      | ^~~~
main.c: 関数 ‘main’ 内:
main.c:215:1: 警告: ‘n’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘q’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘i’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘c’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘d’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘t’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘x’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:215:1: 警告: ‘y’ の型をデフォルトの ‘int’ にします [-Wimplicit-int]
main.c:218:9: 警告: 関数 ‘scanf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
  218 |         sca

ソースコード

diff # 

#define M 1000000007

typedef struct{
	int val;
	int type;
	int range_l;
	int range_r;
	int child_l;
	int child_r;
	int nc;
} N;

N ns[101010];
int nn;
ops[101010];

int insadd(int i,int d){
	N*p=ns+i;
	if(p->type=='a'){
		if(ns[p->child_l].nc>ns[p->child_r].nc){
			p->child_r=insadd(p->child_r,d);
			p->range_r++;
			p->nc=ns[p->child_l].nc+ns[p->child_r].nc+2;
			p->val=(ns[p->child_l].val+ns[p->child_r].val)%M;
			return i;
		}
	}
	{
		N*pl=ns+nn++;
		pl->type='l';
		pl->val=d;
		pl->range_l=p->range_r;
		pl->range_r=p->range_r+1;
		pl->nc=0;
		N*pm=ns+nn++;
		pm->type='a';
		pm->child_l=i;
		pm->child_r=nn-2;
		pm->range_l=p->range_l;
		pm->range_r=p->range_r+1;
		pm->nc=p->nc+2;
		pm->val=(p->val+d)%M;
		return nn-1;
	}
}

int insmul(int i,int d){
	N*p=ns+i;
	if(p->type=='a'){
		p->child_r=insmul(p->child_r,d);
		p->range_r++;
		p->nc=ns[p->child_l].nc+ns[p->child_r].nc+2;
		p->val=(ns[p->child_l].val+ns[p->child_r].val)%M;
		return i;
	}
	if(p->type=='m'){
		if(ns[p->child_l].nc>ns[p->child_r].nc){
			p->child_r=insmul(p->child_r,d);
			p->range_r++;
			p->nc++;
			p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
			return i;
		}
	}
	{
		N*pl=ns+nn++;
		pl->type='l';
		pl->val=d;
		pl->range_l=p->range_r;
		pl->range_r=p->range_r+1;
		pl->nc=0;
		N*pm=ns+nn++;
		pm->type='m';
		pm->child_l=i;
		pm->child_r=nn-2;
		pm->range_l=p->range_l;
		pm->range_r=p->range_r+1;
		pm->nc=p->nc+2;
		pm->val=1ll*p->val*d%M;
		return nn-1;
	}
}

int getv(int j,int i){
	N*p;
	while(p=ns+i,p->type!='l'){
		if(j<ns[p->child_l].range_r){
			i=p->child_l;
		}else{
			i=p->child_r;
		}
	}
	return p->val;
}

void setv(int j,int d,int i){
	N*p=ns+i;
	if(p->type=='l'){
		p->val=d;
	}else{
		if(j<ns[p->child_l].range_r){
			setv(j,d,p->child_l);
		}else{
			setv(j,d,p->child_r);
		}
		if(p->type=='m'){
			p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
		}else{
			p->val=(ns[p->child_l].val+ns[p->child_r].val)%M;
		}
	}
}

mtoa(j,i){
	N*p=ns+i;
	if(ns[p->child_l].range_r>j){
		p->child_l=mtoa(j,p->child_l);
		if(p->type=='m'&&ns[p->child_l].type=='a'){
			int ia=p->child_l;
			N*pa=ns+ia;
			p->child_l=pa->child_r;
			p->range_l=ns[p->child_l].range_l;
			p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
			pa->child_r=i;
			pa->range_r=p->range_r;
			pa->val=(ns[pa->child_l].val+p->val)%M;
			return ia;
		}else{
			p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
			return i;
		}
	}
	if(ns[p->child_r].range_l<j){
		p->child_r=mtoa(j,p->child_r);
		if(p->type=='m'&&ns[p->child_r].type=='a'){
			int ia=p->child_r;
			N*pa=ns+ia;
			p->child_r=pa->child_l;
			p->range_r=ns[p->child_r].range_r;
			p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
			pa->child_l=i;
			pa->range_l=p->range_l;
			pa->val=(p->val+ns[ns[ia].child_r].val)%M;
			return ia;
		}else{
			p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
			return i;
		}
	}
	p->type='a';
	p->val=(ns[p->child_l].val+ns[p->child_r].val)%M;
	return i;
}

atom_i(i){
	N*p=ns+i;
	if(ns[p->child_l].type=='a'&&(ns[p->child_r].type!='a'||ns[p->child_l].nc<=ns[p->child_r].nc)){
		int ia=p->child_l;
		N*pa=ns+ia;
		p->child_l=pa->child_r;
		p->range_l=ns[p->child_l].range_l;
		pa->child_r=atom_i(i);
		pa->range_r=ns[p->child_r].range_r;
		pa->val=(ns[pa->child_l].val+ns[pa->child_r].val)%M;
		return ia;
	}
	if(ns[p->child_r].type=='a'){
		int ia=p->child_r;
		N*pa=ns+ia;
		p->child_r=pa->child_l;
		p->range_r=ns[p->child_r].range_r;
		pa->child_l=atom_i(i);
		pa->range_l=ns[pa->child_l].range_l;
		pa->val=(ns[pa->child_l].val+ns[pa->child_r].val)%M;
		return ia;
	}
	p->val=1ll*ns[p->child_l].val*ns[p->child_r].val%M;
	return i;
}

int atom(int j,int i){
	N*p=ns+i;
	if(ns[p->child_l].range_r>j){
		p->child_l=atom(j,p->child_l);
		p->val=(ns[p->child_l].val+ns[p->child_r].val)%M;
		return i;
	}
	if(ns[p->child_r].range_l<j){
		p->child_r=atom(j,p->child_r);
		p->val=(ns[p->child_l].val+ns[p->child_r].val)%M;
		return i;
	}
	p->type='m';
	return atom_i(i);
}

int f(int l,int r,int i){
	N*p=ns+i;
	if(l<=p->range_l&&r>=p->range_r){
		return p->val;
	}
	if(r<=ns[p->child_l].range_r){
		return f(l,r,p->child_l);
	}
	if(l>=ns[p->child_r].range_l){
		return f(l,r,p->child_r);
	}
	{
		int vl=f(l,r,p->child_l);
		int vr=f(l,r,p->child_r);
		return p->type=='m' ? 1ll*vl*vr%M : (vl+vr)%M;
	}
}

main(n,q,i,c,d,t,x,y){
	int root=0;

	scanf("%d",&n);
	scanf("%d",&d);
	{
		N*p=ns+nn++;
		p->val=d;
		p->type='l';
		p->range_l=0;
		p->range_r=1;
		p->child_l=0;
		p->child_r=0;
		p->nc=0;
		}
	for(i=1;i<n;i+=2){
		c=0;
		scanf(" %s%d",&c,&d);
		if(c=='*'){
			root=insmul(root,d);
		}else{
			root=insadd(root,d);
		}
		ops[i+1]=c;
	}

	scanf("%d",&q);
	for(i=0;i<q;++i){
		t=0;
		scanf(" %s%d%d",&t,&x,&y);
		if(t=='!'){
			if(x%2){
				// digit
				int d1=getv(x/2,root);
				int d2=getv(y/2,root);
				setv(x/2,d2,root);
				setv(y/2,d1,root);
			}else{
				// op
				if(ops[x]!=ops[y]){
					if(ops[y]=='*')t=x;x=y;y=t;
					root=mtoa(x/2,root); ops[x]='*';
					root=atom(y/2,root); ops[y]='+';
				}
			}
		}else{
			printf("%d\n",f(x/2,y/2+1,root));
		}
	}
}
0