Submission #493867

#	Time	Username	Problem	Language	Result	Execution time	Memory
493867		leaked	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	172 ms	43240 KiB

lucky

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#pragma GCC optimize("Ofast")

using namespace std;
const int N=1e5+1;
const int M=1e9+7;
void add(int &a,int b){
    a+=b;
    if(a>=M)
        a-=M;
    else if(a<0)
        a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int sm1[3][3];
int sm2[3][3];
struct node{
    int dp[3][3][3];
    node(){
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++)
                dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;
        }
    }
    void clr(){
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++)
                dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;
        }
    }
};
node mg(const node &a,const node &b){
    node c;
    for(int f=0;f<=2;f++){
        for(int d=0;d<=2;d++){
            sm1[d][f]=sm2[d][f]=0;
            for(int j=0;j<=2;j++)
                add(sm1[d][f],a.dp[d][j][f]),add(sm2[d][f],b.dp[j][d][f]);
        }
    }
    for(int f=0;f<=2;f++){
        for(int s=0;s<=2;s++){
            for(int d1=0;d1<=2;d1++){
                for(int d2=0;d2<=2;d2++){
                    int nf=(f!=1?f:s);
                    add(c.dp[d1][d2][nf],mult(sm1[d1][f],sm2[d2][s]));
                    add(c.dp[d1][d2][nf],-mult(a.dp[d1][0][f],b.dp[1][d2][s]));
                }
            }
        }
    }
    return c;
}

int gd(int x){
    if(x==1)
        return 0;
    if(x==3)
        return 1;
    return 2;
}
node t[4*N];
int a[N];
void build(int v,int tl,int tr){
    if(tl==tr){
        for(int j=0;j<=9;j++){
            int f=(j>a[tl]?2:a[tl]==j);
            add(t[v].dp[gd(j)][gd(j)][f],1);
        }
    }
    else{
        int tm=(tl+tr)>>1;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=mg(t[2*v],t[2*v+1]);
    }
}
void upd(int i,int x,int v,int tl,int tr){
    if(tl==tr){
        t[v].clr();
        a[i]=x;
        for(int j=0;j<=9;j++){
            int f=(j>a[tl]?2:a[tl]==j);
            add(t[v].dp[gd(j)][gd(j)][f],1);
        }
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=i)
        upd(i,x,2*v,tl,tm);
    else
        upd(i,x,2*v+1,tm+1,tr);
    t[v]=mg(t[2*v],t[2*v+1]);
}
node ans;
bool is=0;
void get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
        if(is)
            ans=mg(ans,t[v]);
        else
            ans=t[v];
        is=1;
        return;
    }
    if(tl>r||tr<l)
        return;
    int tm=(tl+tr)>>1;
    get(l,r,2*v,tl,tm);
    get(l,r,2*v+1,tm+1,tr);
    return;
}
int eval(){
    int me=0;
    for(int f=0;f<=1;f++){
        for(int x=0;x<=2;x++)
            for(int y=0;y<=2;y++)
                add(me,ans.dp[x][y][f]);
    }
    return me;
}
signed main(){
    fast_rmi;
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
    }
    build(1,0,n-1);
    ans=t[1];
    cout<<eval()<<'\n';
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            is=0;
            int l,r;
            cin>>l>>r;--l;--r;
            get(l,r,1,0,n-1);
            cout<<eval()<<'\n';
        }
        else{
            int i,x;
            cin>>i>>x;
            upd(i-1,x,1,0,n-1);
        }
    }
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27