oj.uz

Submission #1095201

# Submission time Handle Problem Language Result Execution time Memory
1095201 2024-10-01T14:36:59 Z ASN49K Lucky Numbers (RMI19_lucky) C++14
100 / 100
 129 ms 19716 KB 
#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2124 KB Output is correct
2 Correct 68 ms 2396 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2124 KB Output is correct
2 Correct 68 ms 2396 KB Output is correct
3 Correct 106 ms 15704 KB Output is correct
4 Correct 95 ms 15708 KB Output is correct
5 Correct 119 ms 17752 KB Output is correct
6 Correct 123 ms 19712 KB Output is correct
7 Correct 129 ms 19544 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 52 ms 2124 KB Output is correct
8 Correct 68 ms 2396 KB Output is correct
9 Correct 43 ms 2032 KB Output is correct
10 Correct 56 ms 2500 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 52 ms 2124 KB Output is correct
8 Correct 68 ms 2396 KB Output is correct
9 Correct 106 ms 15704 KB Output is correct
10 Correct 95 ms 15708 KB Output is correct
11 Correct 119 ms 17752 KB Output is correct
12 Correct 123 ms 19712 KB Output is correct
13 Correct 129 ms 19544 KB Output is correct
14 Correct 43 ms 2032 KB Output is correct
15 Correct 56 ms 2500 KB Output is correct
16 Correct 89 ms 15708 KB Output is correct
17 Correct 81 ms 15704 KB Output is correct
18 Correct 98 ms 17776 KB Output is correct
19 Correct 107 ms 19548 KB Output is correct
20 Correct 101 ms 19716 KB Output is correct