oj.uz

Submission #313866

# Submission time Handle Problem Language Result Execution time Memory
313866 2020-10-17T07:40:59 Z MKopchev Lucky Numbers (RMI19_lucky) C++14
28 / 100
 200 ms 1680 KB 
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42,mod=1e9+7;

int n,q;

int inp[nmax];

int LHS,RHS;

int dp[nmax][10][2];

int rec(int pos,int last_digit,int anything)
{
    if(pos>RHS)return 1;

    if(dp[pos-LHS][last_digit][anything]!=-1)return dp[pos-LHS][last_digit][anything];

    int ret=0;

    if(anything==0)
    {
        for(int cur=0;cur<=inp[pos];cur++)
            if(last_digit==1&&cur==3)continue;
            else
            {
                ret=ret+rec(pos+1,cur,cur<inp[pos]);
                if(ret>=mod)ret=ret-mod;
            }
    }
    else
    {
        for(int cur=0;cur<=9;cur++)
            if(last_digit==1&&cur==3)continue;
            else
            {
                ret=ret+rec(pos+1,cur,1);
                if(ret>=mod)ret=ret-mod;
            }
    }

    dp[pos-LHS][last_digit][anything]=ret;

    return ret;
}
int query(int l,int r)
{
    LHS=l;
    RHS=r;

    for(int t=0;t<=RHS-LHS+1;t++)
        for(int dig=0;dig<10;dig++)
            for(int low=0;low<2;low++)
                dp[t][dig][low]=-1;

    return rec(LHS,0,0);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin>>n>>q;

    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        inp[i]=c-'0';
    }

    cout<<query(1,n)<<"\n";

    for(int i=1;i<=q;i++)
    {
        int type;
        cin>>type;

        if(type==2)
        {
            int pos,val;
            cin>>pos>>val;

            inp[pos]=val;
        }
        else
        {
            int l,r;
            cin>>l>>r;

            cout<<query(l,r)<<"\n";
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 1680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 1680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Execution timed out 1093 ms 1680 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Execution timed out 1093 ms 1680 KB Time limit exceeded
8 Halted 0 ms 0 KB -