oj.uz

Submission #1095200

# Submission time Handle Problem Language Result Execution time Memory
1095200 2024-10-01T14:26:03 Z ASN49K Lucky Numbers (RMI19_lucky) C++14
46 / 100
 200 ms 15868 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 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)
    {
        this->n=n;
        aint.resize(4*n+1);
    }
    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);
    for(int i=0;i<n;i++)
    {
        aint.update(i,s[i]-'0');
    }

    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:147:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  147 | main()
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 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 0 ms 348 KB Output is correct
2 Correct 0 ms 456 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 348 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 83 ms 2120 KB Output is correct
2 Correct 111 ms 2392 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2120 KB Output is correct
2 Correct 111 ms 2392 KB Output is correct
3 Execution timed out 458 ms 15868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 83 ms 2120 KB Output is correct
8 Correct 111 ms 2392 KB Output is correct
9 Correct 71 ms 1884 KB Output is correct
10 Correct 94 ms 2392 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 83 ms 2120 KB Output is correct
8 Correct 111 ms 2392 KB Output is correct
9 Execution timed out 458 ms 15868 KB Time limit exceeded
10 Halted 0 ms 0 KB -