Submission #851019

#	Time	Username	Problem	Language	Result	Execution time	Memory
851019		alexdd	Lucky Numbers (RMI19_lucky)	C++17	28 / 100	16 ms	27228 KiB

lucky

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
string s;
int n,cntq;
int nr[100005];
int dp[100005][10];
void calc_nr()
{
    dp[0][0]=1;
    nr[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(j!=3)
            {
                dp[i][j]=nr[i-1];
            }
            nr[i]+=dp[i][j];
            nr[i]%=MOD;
        }
        dp[i][3] += (MOD + nr[i-1] - dp[i-1][1])%MOD;
        dp[i][3]%=MOD;
        nr[i]+=dp[i][3];
        nr[i]%=MOD;
        //cout<<i<<" "<<nr[i]<<" zzz\n";
    }
}
///nr1[i] = nr1[i-1] + nr[i-1] * 8
struct node
{
    int l,r;
    int cnt;
    int cnt1;
    int cnt3;
    int cnt31;
    int isgood=1;
};
node emp={-1,-1,-1,-1,-1,-1,0};
node combine(node x, node y)
{
    if(x.cnt==-1)
        return y;
    if(y.cnt==-1)
        return x;
    node rez;
    rez.cnt=0;
    rez.cnt1=0;
    rez.cnt3=0;
    rez.cnt31=0;
    rez.isgood=1;
    rez.l = x.l;
    rez.r = y.r;
    if(s[x.r]=='1' && s[y.l]=='3')
        rez.isgood=0;

    if(s[x.r]=='1')
    {
        rez.cnt = (rez.cnt + y.cnt - y.cnt3 + MOD)%MOD;
        rez.cnt1 = (rez.cnt1 + y.cnt1 - y.cnt31 + MOD)%MOD;
        if(s[x.l]=='3')
        {
            rez.cnt3 = (rez.cnt3 + rez.cnt)%MOD;
            rez.cnt31 = (rez.cnt31 + rez.cnt1)%MOD;
        }
    }
    else
    {
        rez.cnt = (rez.cnt + y.cnt)%MOD;
        rez.cnt1 = (rez.cnt1 + y.cnt1)%MOD;
        if(s[x.l]=='3')
        {
            rez.cnt3 = (rez.cnt3 + rez.cnt)%MOD;
            rez.cnt31 = (rez.cnt31 + rez.cnt1)%MOD;
        }
    }

    rez.cnt = (rez.cnt + (((MOD + x.cnt - x.cnt1)%MOD) * nr[y.r-y.l+1])%MOD)%MOD;
    rez.cnt = (rez.cnt + (x.cnt1 * ((nr[y.r-y.l+1] - nr[y.r-y.l]+MOD)%MOD))%MOD)%MOD;

    rez.cnt1 = (rez.cnt1 + (((x.cnt - x.cnt1 + MOD)%MOD) * nr[y.r-y.l])%MOD)%MOD;
    if(y.r-y.l-1>=0) rez.cnt1 = (rez.cnt1 + (x.cnt1 * ((MOD + nr[y.r-y.l] - nr[y.r-y.l-1])%MOD))%MOD)%MOD;
    else rez.cnt1 = (rez.cnt1 + (x.cnt1 * nr[y.r-y.l])%MOD)%MOD;

    rez.cnt3 = (rez.cnt3 + (((x.cnt3 - x.cnt31+MOD)%MOD) * nr[y.r-y.l+1])%MOD)%MOD;
    rez.cnt3 = (rez.cnt3 + (x.cnt31 * ((nr[y.r-y.l+1] - nr[y.r-y.l]+MOD)%MOD))%MOD)%MOD;

    rez.cnt31 = (rez.cnt31 + (((x.cnt3 - x.cnt31+MOD)%MOD) * nr[y.r-y.l])%MOD)%MOD;
    if(y.r-y.l-1>=0) rez.cnt31 = (rez.cnt31 + (x.cnt31 * ((nr[y.r-y.l] - nr[y.r-y.l-1]+MOD)%MOD)%MOD))%MOD;
    else rez.cnt31 = (rez.cnt31 + (x.cnt31 * nr[y.r-y.l])%MOD)%MOD;

    rez.cnt1 %= MOD;
    rez.cnt31 %= MOD;
    rez.cnt3 %= MOD;
    rez.cnt %= MOD;

    return rez;
}
node getnode(int cif, int poz)
{
    node rez;
    rez.l = poz;
    rez.r = poz;
    rez.cnt = cif;

    if(cif>1) rez.cnt1 = 1;
    else rez.cnt1 = 0;

    if(cif>3) rez.cnt3 = 1;
    else rez.cnt3 = 0;

    rez.cnt31 = 0;
    rez.isgood = 1;
    return rez;
}
node aint[410005];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod]=getnode(s[st]-'0',st);
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
void upd(int nod, int st, int dr, int poz, int cif)
{
    if(st==dr)
    {
        aint[nod]=getnode(cif,st);
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,cif);
    else upd(nod*2+1,mij+1,dr,poz,cif);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return emp;
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>cntq;
    calc_nr();
    cin>>s;
    build(1,0,n-1);
    int tip,a,b;
    node aux;
    cout<<(aint[1].cnt + aint[1].isgood)%MOD<<"\n";
    for(int i=0;i<cntq;i++)
    {
        cin>>tip>>a>>b;
        if(tip==1)
        {
            a--;
            b--;
            aux = qry(1,0,n-1,a,b);
            cout<<(aux.cnt + aux.isgood)%MOD<<"\n";
        }
        else
        {
            a--;
            s[a]=b+'0';
            upd(1,0,n-1,a,b);
        }
    }
    return 0;
}

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