oj.uz

Submission #640424

# Submission time Handle Problem Language Result Execution time Memory
640424 2022-09-14T15:41:06 Z danikoynov Lucky Numbers (RMI19_lucky) C++14
100 / 100
 56 ms 8732 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]) % mod;
        }
        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 8032 KB Output is correct
3 Correct 8 ms 8020 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 8032 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct
4 Correct 7 ms 8032 KB Output is correct
5 Correct 9 ms 8032 KB Output is correct
6 Correct 9 ms 8020 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8216 KB Output is correct
2 Correct 49 ms 8328 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8216 KB Output is correct
2 Correct 49 ms 8328 KB Output is correct
3 Correct 39 ms 8564 KB Output is correct
4 Correct 43 ms 8528 KB Output is correct
5 Correct 45 ms 8616 KB Output is correct
6 Correct 56 ms 8732 KB Output is correct
7 Correct 50 ms 8632 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8020 KB Output is correct
2 Correct 9 ms 8032 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct
4 Correct 7 ms 8032 KB Output is correct
5 Correct 9 ms 8032 KB Output is correct
6 Correct 9 ms 8020 KB Output is correct
7 Correct 34 ms 8216 KB Output is correct
8 Correct 49 ms 8328 KB Output is correct
9 Correct 24 ms 8256 KB Output is correct
10 Correct 29 ms 8288 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8020 KB Output is correct
2 Correct 9 ms 8032 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct
4 Correct 7 ms 8032 KB Output is correct
5 Correct 9 ms 8032 KB Output is correct
6 Correct 9 ms 8020 KB Output is correct
7 Correct 34 ms 8216 KB Output is correct
8 Correct 49 ms 8328 KB Output is correct
9 Correct 39 ms 8564 KB Output is correct
10 Correct 43 ms 8528 KB Output is correct
11 Correct 45 ms 8616 KB Output is correct
12 Correct 56 ms 8732 KB Output is correct
13 Correct 50 ms 8632 KB Output is correct
14 Correct 24 ms 8256 KB Output is correct
15 Correct 29 ms 8288 KB Output is correct
16 Correct 27 ms 8500 KB Output is correct
17 Correct 29 ms 8508 KB Output is correct
18 Correct 34 ms 8528 KB Output is correct
19 Correct 39 ms 8588 KB Output is correct
20 Correct 32 ms 8608 KB Output is correct