Submission #1093291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093291		alexdd	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	158 ms	26192 KiB

lucky

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
struct node
{
    int cnt[2][2];//daca e egal si il face mai mic acum
    int deja[2][2];//daca e deja mai mic
    int lun;
    bool has13;
    int vle,vri;
};
node combine(node x, node y)
{
    if(x.lun==-1)
        return y;
    if(y.lun==-1)
        return x;
    ///1 - periculos
    node aux;
    aux.lun = x.lun + y.lun;
    aux.vle = x.vle;
    aux.vri = y.vri;
    aux.has13 = (x.has13 | y.has13);
    if(x.vri==1 && y.vle==3) aux.has13=1;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            aux.cnt[i][j]=aux.deja[i][j]=0;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            aux.deja[i][j] += (x.deja[i][0]*(y.deja[0][j]+y.deja[1][j]) + x.deja[i][1]*y.deja[0][j])%MOD;

            aux.cnt[i][j] += (x.cnt[i][0]*(y.deja[0][j]+y.deja[1][j]) + x.cnt[i][1]*y.deja[0][j])%MOD;

        }
        if(!x.has13)
        {
            if(x.vle==3)
            {
                if(x.vri==1)
                    aux.cnt[1][i] += y.cnt[0][i];
                else
                    aux.cnt[1][i] += y.cnt[0][i] + y.cnt[1][i];
            }
            else
            {
                if(x.vri==1)
                    aux.cnt[0][i] += y.cnt[0][i];
                else
                    aux.cnt[0][i] += y.cnt[0][i] + y.cnt[1][i];
            }
        }
    }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            aux.cnt[i][j]%=MOD, aux.deja[i][j]%=MOD;
    return aux;
}
node fa_nod(int cif)
{
    node aux;

    aux.lun = 1;
    aux.vle = aux.vri = cif;
    aux.has13 = 0;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            aux.cnt[i][j] = aux.deja[i][j] = 0;

    for(int i=0;i<10;i++)
    {
        if(i==1)
            aux.deja[0][1]++;
        else if(i==3)
            aux.deja[1][0]++;
        else
            aux.deja[0][0]++;
        if(i < cif)
        {
            if(i==1)
                aux.cnt[0][1]++;
            else if(i==3)
                aux.cnt[1][0]++;
            else
                aux.cnt[0][0]++;
        }
    }
    return aux;
}
node emp = {{{-1,-1},{-1,-1}},{{-1,-1},{-1,-1}},-1,0,-1,-1};

node aint[270000];
void upd(int nod, int st, int dr, int poz, int newv)
{
    if(st==dr)
    {
        aint[nod] = fa_nod(newv);
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    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));
}
int n,q;
int a[100005];
void afis(int x, int y)
{
    node aux = qry(1,1,n,x,y);
    int rez=0;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            rez = (rez + aux.cnt[i][j])%MOD;
    if(!aux.has13) rez = (rez+1)%MOD;
    cout<<rez<<"\n";
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    char ch;
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        a[i] = ch-'0';
        upd(1,1,n,i,a[i]);
    }
    afis(1,n);
    int tip,x,y;
    while(q--)
    {
        cin>>tip>>x>>y;
        if(tip==1)
        {
            afis(x,y);
        }
        else
        {
            upd(1,1,n,x,y);
        }
    }
    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