oj.uz

Submission #199046

# Submission time Handle Problem Language Result Execution time Memory
199046 2020-01-28T18:55:29 Z Andrei_Cotor Lucky Numbers (RMI19_lucky) C++14
28 / 100
 17 ms 1144 KB 
//aparent substring e subsecventa, nu subsir
#include<iostream>
#define MOD 1000000007

using namespace std;

class dynamic
{
public:

    int Dp[2][2],len; //prima-pe primu 3, a doua-pe ultimu 1
    int st,dr;
    bool eq; //posibil ca nr sa fie egal cu cel din secventa

    void init(int x)
    {
        Dp[0][0]=Dp[0][1]=Dp[1][0]=Dp[1][1]=0;

        len=1;
        eq=1;

        int nr=0;
        if(x>1)
        {
            nr++;
            Dp[0][1]=1;
        }

        if(x>3)
        {
            nr++;
            Dp[1][0]=1;
        }

        Dp[0][0]=x-nr;
    }

    int get_val()
    {
        int rez=0;
        for(int i=0; i<=1; i++)
            for(int j=0; j<=1; j++)
                rez=(rez+Dp[i][j])%MOD;

        if(eq)
            rez=(rez+1)%MOD;

        return rez;
    }
};

int Nr[100005][2][2];
int Val[100005];

void comb(dynamic &A, dynamic B)
{
    dynamic aux;
    aux.Dp[0][0]=aux.Dp[0][1]=aux.Dp[1][0]=aux.Dp[1][1]=0;
    aux.len=A.len+B.len;
    aux.st=A.st;
    aux.dr=B.dr;

    aux.eq=A.eq&B.eq;
    if(Val[A.dr]==1 && Val[B.st]==3)
        aux.eq=0;

    //A<, B-oricat
    for(int i=0; i<=1; i++)
    {
        for(int j=0; j<=1; j++)
        {
            for(int ii=0; ii<=1; ii++)
            {
                for(int jj=0; jj<=1; jj++)
                {
                    if(j==1 && ii==1)
                        continue;
                    aux.Dp[i][jj]=(aux.Dp[i][jj]+((1LL*A.Dp[i][j]*Nr[B.len][ii][jj])%MOD))%MOD;
                }
            }
        }
    }

    //A=, B<
    if(!A.eq)
        return;

    for(int i=0; i<=1; i++)
    {
        for(int j=0; j<=1; j++)
        {
            if(Val[A.dr]==1 && i==1)
                continue;

            aux.Dp[Val[A.st]==3][j]=(aux.Dp[Val[A.st]==3][j]+B.Dp[i][j])%MOD;
        }
    }

    A=aux;
}

dynamic Aint[400005];

void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        Aint[nod].init(Val[st]);
        Aint[nod].st=st;
        Aint[nod].dr=dr;
        return;
    }

    int mij=(st+dr)/2;
    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);

    Aint[nod]=Aint[2*nod];
    comb(Aint[nod],Aint[2*nod+1]);
}

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        Val[st]=val;
        Aint[nod].init(val);
        return;
    }

    int mij=(st+dr)/2;
    if(poz<=mij)
        update(2*nod,st,mij,poz,val);
    else
        update(2*nod+1,mij+1,dr,poz,val);

    Aint[nod]=Aint[2*nod];
    comb(Aint[nod],Aint[2*nod+1]);
}

dynamic rez;
bool primu;

void query(int nod, int st, int dr, int l, int r)
{
    if(l<=st && dr<=r)
    {
        if(primu)
        {
            primu=false;
            rez=Aint[nod];
        }
        else
            comb(rez,Aint[nod]);

        return;
    }

    int mij=(st+dr)/2;
    if(l<=mij)
        query(2*nod,st,mij,l,r);
    if(mij<r)
        query(2*nod+1,mij+1,dr,l,r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,q;
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        char c;
        cin>>c;
        Val[i]=c-'0';
    }

    Nr[0][0][0]=1;
    for(int i=1; i<=n; i++)
    {
        for(int c=0; c<=9; c++)
        {
            if(c==1)
            {
                Nr[i][0][1]=(Nr[i][0][1]+((Nr[i-1][0][0]+Nr[i-1][0][1])%MOD))%MOD;
                Nr[i][1][1]=(Nr[i][1][1]+((Nr[i-1][1][1]+Nr[i-1][1][0])%MOD))%MOD;
            }
            else if(c==3)
            {
                if(i==1)
                    Nr[i][1][0]=1;
                else
                {
                    Nr[i][0][0]=(Nr[i][0][0]+Nr[i-1][0][0])%MOD;
                    Nr[i][1][0]=(Nr[i][1][0]+Nr[i-1][1][0])%MOD;
                }
            }
            else
            {
                Nr[i][0][0]=(Nr[i][0][0]+((Nr[i-1][0][0]+Nr[i-1][0][1])%MOD))%MOD;
                Nr[i][1][0]=(Nr[i][1][0]+((Nr[i-1][1][0]+Nr[i-1][1][1])%MOD))%MOD;
            }
        }
    }

    build(1,1,n);

    primu=true;
    query(1,1,n,1,n);

    cout<<rez.get_val()<<"\n";

    for(int i=1; i<=q; i++)
    {
        int tip,x,y;
        cin>>tip>>x>>y;

        if(tip==1)
        {
            primu=true;
            query(1,1,n,x,y);

            cout<<rez.get_val()<<"\n";
        }
        else
            update(1,1,n,x,y);
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Incorrect 17 ms 1144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Incorrect 17 ms 1144 KB Output isn't correct
8 Halted 0 ms 0 KB -