結果

問題 No.619 CardShuffle
ユーザー ryoissy
提出日時 2018-01-25 12:05:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 173 ms / 3,000 ms
コード長 4,428 bytes
コンパイル時間 3,114 ms
コンパイル使用メモリ 164,224 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2024-12-26 15:33:36
合計ジャッジ時間 7,172 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:165:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  165 |         scanf("%d%*c",&n);
      |         ~~~~~^~~~~~~~~~~~
main.cpp:169:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  169 |                 scanf("%c%*c",&c);
      |                 ~~~~~^~~~~~~~~~~~
main.cpp:185:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  185 |         scanf("%d%*c",&q);
      |         ~~~~~^~~~~~~~~~~~
main.cpp:189:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  189 |                 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;
        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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0