oj.uz

Submission #640423

# Submission time Handle Problem Language Result Execution time Memory
640423 2022-09-14T15:40:10 Z danikoynov Lucky Numbers (RMI19_lucky) C++14
28 / 100
 31 ms 8324 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;

ll dp[maxn][10];
int n, q;
string num;
ll query(int l, int r)

{
    char c = num[l - 1];
    num[l - 1] = '#';
    ll ans = 0;
    bool fine = true;
    for (int j = l; j <= r; j ++)
    {
        for (int d = 0; d < (int)(num[j] - '0'); d ++)
        {
            if (num[j - 1] == '1' && d == 3)
                continue;
            ans = (ans + dp[r - j + 1][d]);
        }
        if (num[j - 1] == '1' && num[j] == '3')
        {
            fine = false;
            break;
        }
    }
    if (fine)
        ans = (ans + 1) % mod;
    num[l - 1] = c;
    return ans;
}
void solve()
{
    cin >> n >> q >> num;
    for (int i = 0; i < 10; i ++)
        dp[1][i] = 1;

    for (int i = 2; i < maxn; i ++)
    {
        ll sum = 0;
        for (int j = 0; j < 10; j ++)
            sum = (sum + dp[i - 1][j]) % mod;
        for (int j = 0; j < 10; j ++)
        {
            dp[i][j] = sum;
            if (j == 1)
                dp[i][j] = (dp[i][j] - dp[i - 1][3] + mod) % mod;
        }
    }

    num = "#" + num;
    cout << query(1, n) << endl;
    int type, l, r, pos, dig;
    for (int t = 1; t <= q; t ++)
    {
        cin >> type;
        if (type == 1)
        {
            cin >> l >> r;
            cout << query(l, r) << endl;
        }
        else
        {
            cin >> pos >> dig;
            num[pos] = (char)(dig + '0');
        }
    }
}

int main()
{
    solve();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8020 KB Output is correct
2 Correct 9 ms 8132 KB Output is correct
3 Correct 7 ms 8052 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8020 KB Output is correct
2 Correct 9 ms 8132 KB Output is correct
3 Correct 7 ms 8052 KB Output is correct
4 Correct 8 ms 8020 KB Output is correct
5 Correct 8 ms 8116 KB Output is correct
6 Correct 7 ms 8020 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 8324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 8324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8020 KB Output is correct
2 Correct 9 ms 8132 KB Output is correct
3 Correct 7 ms 8052 KB Output is correct
4 Correct 8 ms 8020 KB Output is correct
5 Correct 8 ms 8116 KB Output is correct
6 Correct 7 ms 8020 KB Output is correct
7 Incorrect 31 ms 8324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8020 KB Output is correct
2 Correct 9 ms 8132 KB Output is correct
3 Correct 7 ms 8052 KB Output is correct
4 Correct 8 ms 8020 KB Output is correct
5 Correct 8 ms 8116 KB Output is correct
6 Correct 7 ms 8020 KB Output is correct
7 Incorrect 31 ms 8324 KB Output isn't correct
8 Halted 0 ms 0 KB -