結果

問題 No.619 CardShuffle
ユーザー ryoissyryoissy
提出日時 2018-01-25 03:19:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,924 bytes
コンパイル時間 1,943 ms
コンパイル使用メモリ 173,036 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-06-08 01:06:44
合計ジャッジ時間 5,744 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 AC 146 ms
12,160 KB
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 value{
	ll sum=0,l=0,r=0;
	int flag=0;
	value(){}
	value(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;
	value val[1<<18];

	void update(int k,ll v){
		k+=N-1;
		val[k]=value(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(fie[(nl+nr)/2-1]==0){
				val[k]=value((val[k*2+1].sum+val[k*2+2].sum)%MOD,val[k*2+1].l,val[k*2+2].r,0);
			}else{
				value vl=val[k*2+1];
				value vr=val[k*2+2];
				if(vl.flag==1 && vr.flag==1){
					val[k]=value(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
				}else if(vl.flag==1){
					val[k]=value((vl.sum*vr.l+vr.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
				}else if(vr.flag==1){
					val[k]=value((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
				}else{
					val[k]=value((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;
			}
			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]=value((val[k*2+1].sum+val[k*2+2].sum)%MOD,val[k*2+1].l,val[k*2+2].r,0);
			}else{
				value vl=val[k*2+1];
				value vr=val[k*2+2];
				if(vl.flag==1 && vr.flag==1){
					val[k]=value(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
				}else if(vl.flag==1){
					val[k]=value((vl.sum*vr.l+vr.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
				}else if(vr.flag==1){
					val[k]=value((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
				}else{
					val[k]=value((vl.r*vr.l+vl.l+vr.r)%MOD,vl.l,vr.r,0);
				}
			}
		}
		//printf("\n");
	}
	value 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 value(0,0,0,-1);
		if(a<=l && r<=b)return val[k];
		int mid=(l+r)/2;
		value vl=query(a,b,k*2+1,l,mid);
		value 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 value(vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,vl.sum*vr.sum%MOD,1);
			}
			if(vl.flag==1){
				return value((vl.sum*vr.l+vr.r)%MOD,vl.sum*vr.l%MOD,vr.r,0);
			}
			if(vr.flag==1){
				return value((vl.r*vr.sum+vl.l)%MOD,vl.l,vr.sum*vl.r%MOD,0);
			}
			return value((vl.r*vr.l+vl.l+vr.r)%MOD,vl.l,vr.r,0);
		}else{
			return value((vl.sum+vr.sum)%MOD,vl.l,vr.r,0);
		}
	}
};

int va[1000000];
segtree seg;

int main(void){
	scanf("%d%*c",&n);
	for(int i=0;i<n;i++){
		char c;
		scanf("%c%*c",&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