結果

問題 No.619 CardShuffle
コンテスト
ユーザー ryoissy
提出日時 2018-01-25 11:56:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,436 bytes
コンパイル時間 2,644 ms
コンパイル使用メモリ 163,964 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-12-26 15:33:15
合計ジャッジ時間 7,656 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22 WA * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:166:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  166 |         scanf("%d%*c",&n);
      |         ~~~~~^~~~~~~~~~~~
main.cpp:170:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  170 |                 scanf("%c%*c",&c);
      |                 ~~~~~^~~~~~~~~~~~
main.cpp:186:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  186 |         scanf("%d%*c",&q);
      |         ~~~~~^~~~~~~~~~~~
main.cpp:190:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  190 |                 scanf("%c%d%d%*c",&qe,&l,&r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct valu{
	ll sum=0,l=0,r=0;
	int flag=-1;
	valu(){
	}
	valu(ll a,ll b,ll c,int f){
		sum=a;
		l=b;
		r=c;
		flag=f;
	}
};

int n;
int fie[1000000];

struct segtree{
	static const int N=1<<17;
	valu val[1<<18];

	void update(int k,ll v){
		k+=N-1;
		val[k]=valu(v,v,v,1);
		int nl=k-N+1,nr=k+1-N+1;
		int s=1;
		while(k>0){
			int pr=k;
			k=(k-1)/2;
			if(pr==k*2+1){
				nr+=s;
			}else{
				nl-=s;
			}
			s*=2;
			if(nl<0 || nr>N){
				puts("error\n");
			}
			if(val[k*2+1].flag==-1){
				val[k]=val[k*2+2];
			}else if(val[k*2+2].flag==-1){
				val[k]=val[k*2+1];
			}else if(fie[(nl+nr)/2-1]==0){
				val[k]=valu((val[k*2+1].sum+val[k*2+2].sum)%MOD,val[k*2+1].l,val[k*2+2].r,0);
			}else{
				valu vl=val[k*2+1];
				valu vr=val[k*2+2];
				if(vl.flag==1 && vr.flag==1){
					val[k]=valu(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
				}else if(vl.flag==1){
					val[k]=valu((vl.sum*vr.l+vr.sum-vr.l+MOD)%MOD,vl.sum*vr.l%MOD,vr.r,0);
				}else if(vr.flag==1){
					val[k]=valu((vl.r*vr.sum+vl.sum-vl.r+MOD)%MOD,vl.l,vr.sum*vl.r%MOD,0);
				}else{
					val[k]=valu((vl.r*vr.l+vl.sum-vl.r+vr.sum-vr.l+2LL*MOD)%MOD,vl.l,vr.r,0);
				}
			}
			//printf("%d %lld %d %d %lld %lld %lld\n",k,v,nl,nr,val[k].sum,val[k*2+1].sum,val[k*2+2].sum);
		}
	}

	void update2(int v){
		stack<int> st;
		int l=0,r=N;
		int k=0;
		int s=N;
		while(1){
			st.push(k);
			if(v<(l+r)/2-1){
				r=(l+r)/2;
				k=k*2+1;
			}else if(v==(l+r)/2-1){
				break;
			}else if(v>(l+r)/2-1){
				l=(l+r)/2;
				k=k*2+2;
			}
			s/=2;
		}
		//printf("%d %d %d\n",l,r,v);
		int nl=l,nr=r;
		int pr=-1;
		s/=2;
		while(st.size()){
			k=st.top();
			//printf("%d ",k);
			st.pop();
			if(pr!=-1){
				if(pr==k*2+1){
					nr+=s;
				}else{
					nl-=s;
				}
				s*=2;
			}
			if(nl<0 || nr>N){
				puts("error\n");
			}
			pr=k;
			//printf("%d %d %d %d %lld %lld ",nl,nr,(nl+nr)/2-1,fie[(nl+nr)/2-1],val[k*2+1].sum,val[k*2+2].sum);
			if(val[k*2+1].flag==-1){
				val[k]=val[k*2+2];
			}else if(val[k*2+2].flag==-1){
				val[k]=val[k*2+1];
			}else if(fie[(nl+nr)/2-1]==0){
				val[k]=valu((val[k*2+1].sum+val[k*2+2].sum)%MOD,val[k*2+1].l,val[k*2+2].r,0);
			}else{
				valu vl=val[k*2+1];
				valu vr=val[k*2+2];
				if(vl.flag==1 && vr.flag==1){
					val[k]=valu(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
				}else if(vl.flag==1){
					val[k]=valu((vl.sum*vr.l+vr.sum-vr.l+MOD)%MOD,vl.sum*vr.l%MOD,vr.r,0);
				}else if(vr.flag==1){
					val[k]=valu((vl.r*vr.sum+vl.sum-vl.r+MOD)%MOD,vl.l,vr.sum*vl.r%MOD,0);
				}else{
					val[k]=valu((vl.r*vr.l+vl.sum-vl.r+vr.sum-vr.l+2LL*MOD)%MOD,vl.l,vr.r,0);
				}
			}
		}
		//printf("\n");
	}
	valu query(int a,int b,int k=0,int l=0,int r=N){
		//printf("%d %d %lld\n",l,r,val[k].sum);
		if(b<=l || r<=a)return valu(0,0,0,-1);
		if(a<=l && r<=b){
			//printf("%d %d %lld\n",l,r,val[k].sum);
			return val[k];
		}
		int mid=(l+r)/2;
		valu vl=query(a,b,k*2+1,l,mid);
		valu vr=query(a,b,k*2+2,mid,r);
		//printf("%d %d %lld %lld\n",l,r,vl.sum,vr.sum);
		if(vl.flag==-1){
			return vr;
		}
		if(vr.flag==-1){
			return vl;
		}
		if(fie[mid-1]==1){
			if(vl.flag==1 && vr.flag==1){
				return valu(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
			}
			if(vl.flag==1){
				return valu((vl.sum*vr.l+vr.sum-vr.l+MOD)%MOD,vl.sum*vr.l%MOD,vr.r,0);
			}
			if(vr.flag==1){
				return valu((vl.r*vr.sum+vl.sum-vl.r+MOD)%MOD,vl.l,vr.sum*vl.r%MOD,0);
			}
			return valu((vl.r*vr.l+vl.sum-vl.r+vr.sum-vr.l+2LL*MOD)%MOD,vl.l,vr.r,0);
		}else{
			return valu((vl.sum+vr.sum)%MOD,vl.l,vr.r,0);
		}
	}
};

int va[1000000];
segtree seg;

int main(void){
	scanf("%d%*c",&n);
	//printf("%d\n",n);
	for(int i=0;i<n;i++){
		char c;
		scanf("%c%*c",&c);
		//printf("%c\n",c);
		if(i%2==0){
			va[i/2]=(c-'0');
		}else{
			if(c=='+'){
				fie[i/2]=0;
			}else{
				fie[i/2]=1;
			}
		}
	}
	for(int i=0;i<(n+1)/2;i++){
		seg.update(i,va[i]);
	}
	int q;
	scanf("%d%*c",&q);
	for(int i=0;i<q;i++){
		char qe;
		int l,r;
		scanf("%c%d%d%*c",&qe,&l,&r);
		if(qe=='!'){
			l--;
			r--;
			if(l%2==0){
				l/=2;
				r/=2;
				swap(va[l],va[r]);
				seg.update(l,va[l]);
				seg.update(r,va[r]);
			}else{
				l/=2;
				r/=2;
				swap(fie[l],fie[r]);
				seg.update2(l);
				seg.update2(r);
			}
		}else{
			l/=2;
			r/=2;
			r++;
			printf("%lld\n",seg.query(l,r).sum);
		}
	}
	return 0;
}
0