#231736 (C++11) No.619 CardShuffle

提出ソース

結果

問題	No.619 CardShuffle
ユーザー	ryoissy
提出日時	2018-01-25 12:05:54
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	149 ms / 3,000 ms
コード長	4,428 bytes
コンパイル時間	1,748 ms
コンパイル使用メモリ	162,124 KB
実行使用メモリ	17,964 KB
最終ジャッジ日時	2023-08-27 05:49:49
合計ジャッジ時間	6,453 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 15,772 KB
testcase_01	AC	6 ms 15,780 KB
testcase_02	AC	6 ms 15,792 KB
testcase_03	AC	5 ms 15,688 KB
testcase_04	AC	6 ms 15,768 KB
testcase_05	AC	6 ms 15,776 KB
testcase_06	AC	6 ms 15,684 KB
testcase_07	AC	6 ms 15,788 KB
testcase_08	AC	6 ms 16,012 KB
testcase_09	AC	6 ms 15,912 KB
testcase_10	AC	6 ms 15,772 KB
testcase_11	AC	6 ms 15,768 KB
testcase_12	AC	6 ms 15,760 KB
testcase_13	AC	6 ms 15,768 KB
testcase_14	AC	6 ms 15,912 KB
testcase_15	AC	6 ms 15,936 KB
testcase_16	AC	137 ms 17,820 KB
testcase_17	AC	119 ms 17,760 KB
testcase_18	AC	137 ms 17,760 KB
testcase_19	AC	120 ms 17,812 KB
testcase_20	AC	139 ms 17,856 KB
testcase_21	AC	136 ms 17,816 KB
testcase_22	AC	113 ms 17,736 KB
testcase_23	AC	136 ms 17,836 KB
testcase_24	AC	114 ms 17,804 KB
testcase_25	AC	149 ms 17,868 KB
testcase_26	AC	133 ms 17,964 KB
testcase_27	AC	120 ms 17,760 KB
testcase_28	AC	131 ms 17,820 KB
testcase_29	AC	120 ms 17,812 KB
testcase_30	AC	125 ms 17,852 KB
testcase_31	AC	6 ms 15,864 KB
testcase_32	AC	141 ms 17,760 KB
testcase_33	AC	135 ms 17,804 KB
testcase_34	AC	110 ms 17,888 KB
testcase_35	AC	53 ms 15,936 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
		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;
}

yukicoder

結果

テストケース

ソースコード