結果

問題 No.619 CardShuffle
ユーザー ryoissyryoissy
提出日時 2018-01-25 03:26:22
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,038 bytes
コンパイル時間 2,378 ms
コンパイル使用メモリ 163,300 KB
実行使用メモリ 14,236 KB
最終ジャッジ日時 2023-08-27 05:12:18
合計ジャッジ時間 7,327 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます

ソースコード

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=0;
	valu(){
	}
	valu(ll a,ll b,ll c,int f){
		sum=a;
		l=b;
		r=c;
		flag=f;
	}
};

int n;
int fie[10000000];

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(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.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
				}else if(vr.flag==1){
					val[k]=valu((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
				}else{
					val[k]=valu((vl.r*vr.l+vl.l+vr.r)%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(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.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
				}else if(vr.flag==1){
					val[k]=valu((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
				}else{
					val[k]=valu((vl.r*vr.l+vl.l+vr.r)%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)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.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
			}
			if(vr.flag==1){
				return valu((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
			}
			return valu((vl.r*vr.l+vl.l+vr.r)%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');
			seg.update(i/2,c-'0');
		}else{
			if(c=='+'){
				fie[i/2]=0;
			}else{
				fie[i/2]=1;
			}
		}
	}
	for(int i=0;i<n/2;i++){
		seg.update2(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));
		}
	}
	return 0;
}
0