Submission #478029

#	Time	Username	Problem	Language	Result	Execution time	Memory
478029		stefantaga	Lucky Numbers (RMI19_lucky)	C++14	28 / 100	19 ms	1348 KiB

lucky

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
struct wow
{
    int are1,are31,are3,ebun,nrcifre;
    int cntbune,cnt1,cnt31,cnt3;
};
wow arb[400005];
int din[100005];
int scade (int x,int y)
{
    return (x-y+MOD)%MOD;
}
int inmult(int x,int y)
{
    return (1LL*x*y)%MOD;
}
int aduna(int x,int y)
{
    return (x+y)%MOD;
}
void initializeaza(wow &x)
{
    x.are1=x.are31=x.are3=x.ebun=x.cntbune=x.cnt1=x.cnt31=x.cnt3=x.nrcifre=0;
}
wow adunawow(wow a,wow b)
{
    wow rez;
    initializeaza(rez);
    rez.nrcifre=a.nrcifre+b.nrcifre;
    if (a.are1==0||b.are3==0)
    {
        if (a.ebun==1&&b.ebun==1)
        {
            rez.ebun=1;
        }
        if (a.are3&&b.are1)
        {
            rez.are31=1;
        }
        if (b.are1)
        {
            rez.are1=1;
        }
        if (a.are3)
        {
            rez.are3=1;
        }
    }
    int nr=b.nrcifre;
    rez.cntbune=scade(aduna(inmult(scade(a.cntbune,a.ebun),din[nr]),inmult(a.ebun,b.cntbune)),aduna(inmult(scade(a.cnt1,a.are1),din[nr-1]),inmult(b.cnt3,a.are1)));
    rez.cnt1=scade(aduna(inmult(scade(a.cntbune,a.ebun),din[nr-1]),inmult(a.ebun,b.cnt1)),aduna(inmult(scade(a.cnt1,a.are1),din[nr-2]),inmult(b.cnt31,a.are1)));
    rez.cnt3=scade(aduna(inmult(scade(a.cnt3,a.are3),din[nr]),inmult(inmult(a.ebun,a.are3),b.cntbune)),aduna(inmult(scade(a.cnt31,a.are31),din[nr-1]),inmult(inmult(a.ebun,a.are31),b.cnt3)));
    rez.cnt31=scade(aduna(inmult(scade(a.cnt3,a.are3),din[nr-1]),inmult(inmult(a.ebun,a.are3),b.cnt1)),aduna(inmult(scade(a.cnt31,a.are31),din[nr-2]),inmult(inmult(a.ebun,a.are31),b.cnt31)));
    return rez;
}
void update(int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        initializeaza(arb[nod]);
        arb[nod].cntbune=val+1;
        arb[nod].ebun=1;
        arb[nod].nrcifre=1;
        if (val==1)
        {
            arb[nod].are1=1;
        }
        if (val>=1)
        {
            arb[nod].cnt1=1;
        }
        if (val>=3)
        {
            arb[nod].cnt3=1;
        }
        if (val==3)
        {
            arb[nod].are3=1;
        }
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod]=adunawow(arb[2*nod],arb[2*nod+1]);
}
wow query(int st,int dr,int nod,int ua,int ub)
{
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    int ok=0,mij=(st+dr)/2;
    wow sum;
    if (ua<=mij)
    {
        sum=query(st,mij,2*nod,ua,ub);
        ok=1;
    }
    if (mij<ub)
    {
        if (ok==0)
        {
            sum=query(mij+1,dr,2*nod+1,ua,ub);
        }
        else
        {
            sum=adunawow(sum,query(mij+1,dr,2*nod+1,ua,ub));
        }
    }
    return sum;
}
int n,m,i,cifra,tip,x,y;
char s[100005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    cin>>s;
    din[0]=1;
    din[1]=10;
    for (i=2;i<=100000;i++)
    {
        din[i]=scade(inmult(din[i-1],10),din[i-2]);
    }
    for (i=0;i<n;i++)
    {
        cifra=s[i]-'0';
        update(1,n,1,i+1,cifra);
    }
    cout<<query(1,n,1,1,n).cntbune<<'\n';
    for (i=1;i<=m;i++)
    {
        cin>>tip>>x>>y;
        if (tip==2)
        {
            update(1,n,1,x,y);
        }
        else
        {
            cout<<query(1,n,1,x,y).cntbune<<'\n';
        }
    }
    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