Submission #1095201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095201		ASN49K	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	129 ms	19716 KiB

lucky

#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
using node=array<array<array<int,2>,2>,3>;
int prod(int x,int y)
{
    return (1LL*x*y)%mod;
}
int add(int x,int y)
{
    return (x+y)%mod;
}
void add_self(int& x,int y)
{
    x+=y;
    x%=mod;
}
void clear(node& a)
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                a[i][j][k]=0;
            }
        }
    }
}
node merge(const node& a,const node& b)
{
    node rez;
    clear(rez);
    for(int tip_a=0;tip_a<3;tip_a++)
    {
        for(int tip_b=0;tip_b<3;tip_b++)
        {
            int new_tip=tip_a;
            if(new_tip==1)
            {
                new_tip=tip_b;
            }
            for(int i=0;i<2;i++)
            {
                for(int j=0;j<2;j++)
                {
                    for(int k1=0;k1<2;k1++)
                    {
                        for(int k2=0;k2<2;k2++)
                        {
                            if((k1&k2)==0)
                            {
                                add_self(rez[new_tip][i][j],prod(a[tip_a][i][k1],b[tip_b][k2][j]));
                            }
                        }
                    }
                }
            }
        }
    }
    return rez;
}
const int N=100'000;

class Aint
{
    int n;
    vector<node>aint;
    void build(int nod,int st,int dr,string& s)
    {
        if(st==dr)
        {
            int val=s[st]-'0';
            clear(aint[nod]);
            aint[nod][1][val==3][val==1]=1;
            for(int i=0;i<val;i++)
            {
                aint[nod][0][i==3][i==1]++;
            }
            for(int i=val+1;i<10;i++)
            {
                aint[nod][2][i==3][i==1]++;
            }
            return;
        }
        int m=(st+dr)/2;
        build(nod<<1,st,m,s);
        build(nod<<1|1,m+1,dr,s);
        aint[nod]=merge(aint[nod<<1] , aint[nod<<1|1]);
    }
    void update(int nod,int st,int dr,int poz,int val)
    {
        if(st==dr)
        {
            clear(aint[nod]);
            aint[nod][1][val==3][val==1]=1;
            for(int i=0;i<val;i++)
            {
                aint[nod][0][i==3][i==1]++;
            }
            for(int i=val+1;i<10;i++)
            {
                aint[nod][2][i==3][i==1]++;
            }
            return;
        }
        int m=(st+dr)/2;
        if(poz<=m)
        {
            update(nod<<1,st,m,poz,val);
        }
        else
        {
            update(nod<<1|1,m+1,dr,poz,val);
        }
        aint[nod]=merge(aint[nod<<1] , aint[nod<<1|1]);
    }

    node query(int nod,int st,int dr,int l,int r)
    {
        if(l>dr || r<st)
        {
            node idk;
            clear(idk);
            idk[1][0][0]=1;
            return idk;
        }
        if(l<=st && dr<=r)
        {
            return aint[nod];
        }
        int m=(st+dr)/2;
        return merge(query(nod<<1,st,m,l,r),query(nod<<1|1,m+1,dr,l,r));
    }
public:
    Aint(int n,string& s)
    {
        this->n=n;
        aint.resize(4*n+1);
        build(1,0,n-1,s);
    }
    void update(int poz,int val)
    {
        update(1,0,n-1,poz,val);
    }
    int query(int l,int r)
    {
        int sol=0;
        node rez=query(1,0,n-1,l,r);
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    add_self(sol , rez[i][j][k]);
                }
            }
        }
        return sol;
    }

};
main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    Aint aint(n,s);
    cout<<aint.query(0,n-1)<<'\n';
    while(q--)
    {
        int cer;
        cin>>cer;
        if(cer==1)
        {
            int l,r;
            cin>>l>>r;
            cout<<aint.query(l-1,r-1)<<'\n';
        }
        else
        {
            int poz,val;
            cin>>poz>>val;
            aint.update(poz-1,val);
        }
    }
}

Compilation message (stderr)

lucky.cpp:170:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  170 | main()
      | ^~~~

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