結果
| 問題 |
No.619 CardShuffle
|
| コンテスト | |
| ユーザー |
 tails
|
| 提出日時 | 2017-12-19 03:54:03 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,068 bytes |
| コンパイル時間 | 452 ms |
| コンパイル使用メモリ | 32,384 KB |
| 実行使用メモリ | 13,772 KB |
| 最終ジャッジ日時 | 2024-12-22 21:46:23 |
| 合計ジャッジ時間 | 39,361 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 WA * 5 TLE * 9 |
コンパイルメッセージ
main.c:15:1: warning: data definition has no type or storage class
15 | ops[101010];
| ^~~
main.c:15:1: warning: type defaults to 'int' in declaration of 'ops' [-Wimplicit-int]
main.c:114:1: warning: return type defaults to 'int' [-Wimplicit-int]
114 | mtoa(j,i){
| ^~~~
main.c: In function 'mtoa':
main.c:114:1: warning: type of 'j' defaults to 'int' [-Wimplicit-int]
main.c:114:1: warning: type of 'i' defaults to 'int' [-Wimplicit-int]
main.c: At top level:
main.c:155:1: warning: return type defaults to 'int' [-Wimplicit-int]
155 | atom_i(i){
| ^~~~~~
main.c: In function 'atom_i':
main.c:155:1: warning: type of 'i' defaults to 'int' [-Wimplicit-int]
main.c: At top level:
main.c:215:1: warning: return type defaults to 'int' [-Wimplicit-int]
215 | main(n,q,i,c,d,t,x,y){
| ^~~~
main.c: In function 'main':
main.c:215:1: warning: type of 'n' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 'q' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 'i' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 'c' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 'd' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 't' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 'x' defaults to 'int' [-Wimplicit-int]
main.c:215:1: warning: type of 'y' defaults to 'int' [-Wimplicit-int]
main.c:218:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
218 | scanf("%d",&n);
| ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
+++ |+#include <stdio.h>
1 | #define M 1000000007
main.c:218:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
218 | scanf("%d",&n);
| ^~~~~
main.c:218:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:261:25: warning: implicit declaration of function 'print
ソースコード
#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));
}
}
}