oj.uz

Submission #477548

# Submission time Handle Problem Language Result Execution time Memory
477548 2021-10-02T15:06:52 Z Alexandruabcde Lucky Numbers (RMI19_lucky) C++14
100 / 100
 190 ms 14232 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;
constexpr int MOD = 1e9 + 7;

int N, Q;
char ch[NMAX];

struct Node {
    int cnt_good;
    int cnt_good_end_1;
    int cnt_good_begin_3;
    int cnt_good_begin_3_end_1;

    int is_good;
    int end_1;
    int begin_3;
    int begin_3_end_1;

    int cnt_digits;

    Node(){}
    Node (int val) {
        cnt_good = val+1;
        cnt_good_end_1 = (val >= 1);
        cnt_good_begin_3 = (val >= 3);
        cnt_good_begin_3_end_1 = 0;

        is_good = 1;
        end_1 = (val==1);
        begin_3 = (val==3);
        begin_3_end_1 = 0;

        cnt_digits = 1;
    }
};

int sum[NMAX];
int dp[NMAX][10];

int PROD (int a, int b) {
    return (1LL * a * b) % MOD;
}
int SCAD (int a, int b) {
    return (a - b + MOD) % MOD;
}
int ADUN (int a, int b) {
    return (a + b) % MOD;
}

void Precalculare () {
    sum[0] = 1;
    sum[1] = 10;
    for (int i = 2; i <= N; ++ i )
        sum[i] = SCAD(PROD(10, sum[i-1]), sum[i-2]);

    for (int i = 0; i <= 9; ++ i )
        dp[1][i] = 1;
    for (int i = 2; i <= N; ++ i ) {
        for (int j = 0; j <= 9; ++ j )
            for (int k = 0; k <= 9; ++ k )
                if (j != 1 || k != 3) dp[i][j] = ADUN(dp[i][j], dp[i-1][k]);
    }
}

Node V[4*NMAX];

Node operator+ (const Node &a, const Node &b) {
    Node res = Node(-1);

    if (a.is_good && b.is_good && (!a.end_1 || !b.begin_3))
        res.is_good = 1;
    else res.is_good = 0;

    if (res.is_good && a.begin_3)
        res.begin_3 = 1;
    else res.begin_3 = 0;

    if (res.is_good && b.end_1)
        res.end_1 = 1;
    else res.end_1 = 0;

    if (res.begin_3 && res.end_1)
        res.begin_3_end_1 = 1;
    else res.begin_3_end_1 = 0;

    res.cnt_digits = a.cnt_digits + b.cnt_digits;

    res.cnt_good = SCAD(ADUN(PROD(SCAD(a.cnt_good, a.is_good), sum[b.cnt_digits]), PROD(a.is_good, b.cnt_good)), ADUN(PROD(SCAD(a.cnt_good_end_1,a.end_1), dp[b.cnt_digits][3]), PROD(a.end_1, b.cnt_good_begin_3)));
    res.cnt_good_begin_3 = SCAD(ADUN(PROD(SCAD(a.cnt_good_begin_3, a.begin_3), sum[b.cnt_digits]), PROD(a.begin_3, b.cnt_good)), ADUN(PROD(SCAD(a.cnt_good_begin_3_end_1,a.begin_3_end_1), dp[b.cnt_digits][3]), PROD(a.begin_3_end_1, b.cnt_good_begin_3)));
    res.cnt_good_end_1 = SCAD(ADUN(PROD(SCAD(a.cnt_good, a.is_good), sum[b.cnt_digits-1]), PROD(a.is_good, b.cnt_good_end_1)), ADUN(PROD(SCAD(a.cnt_good_end_1, a.end_1), dp[b.cnt_digits-1][3]), PROD(a.end_1, b.cnt_good_begin_3_end_1)));
    res.cnt_good_begin_3_end_1 = SCAD(ADUN(PROD(SCAD(a.cnt_good_begin_3, a.begin_3), sum[b.cnt_digits-1]), PROD(a.begin_3, b.cnt_good_end_1)), ADUN(PROD(SCAD(a.cnt_good_begin_3_end_1, a.begin_3_end_1), dp[b.cnt_digits-1][3]), PROD(a.begin_3_end_1, b.cnt_good_begin_3_end_1)));

    return res;
}

void Update (int nod, int a, int b, int pos, int val) {
    if (a == b) {
        V[nod] = Node(val);
        return;
    }

    int mij = (a + b) / 2;

    if (pos <= mij) Update(2*nod, a, mij, pos, val);
    else Update(2*nod+1, mij+1, b, pos, val);

    V[nod] = V[2*nod]+V[2*nod+1];
}

Node Query (int nod, int a, int b, int qa, int qb) {
    if (qa <= a && b <= qb) return V[nod];

    Node st = Node(-1), dr = Node(-1);
    int mij = (a + b) / 2;

    if (qa <= mij) st = Query(2*nod, a, mij, qa, qb);
    if (mij < qb) dr = Query(2*nod+1, mij+1, b, qa, qb);

    if (qa <= mij && mij < qb) return (st + dr);

    if (qa <= mij) return st;

    if (mij < qb) return dr;
}

int Answer (int L, int R) {
    Node q = Query(1, 1, N, L, R);

    return q.cnt_good;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++ i )
        cin >> ch[i];

    Precalculare();

    for (int i = 1; i <= N; ++ i )
        Update(1, 1, N, i, (ch[i]-'0'));

    cout << Answer(1, N) << '\n';
    for (int i = 1; i <= Q; ++ i ) {
        int tip, x, y;
        cin >> tip >> x >> y;

        if (tip == 1)
            cout << Answer(x, y) << '\n';
        else Update(1, 1, N, x, y);
    }

    return 0;
}

Compilation message

lucky.cpp: In function 'Node Query(int, int, int, int, int)':
lucky.cpp:127:1: warning: control reaches end of non-void function [-Wreturn-type]
  127 | }
      | ^

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1364 KB Output is correct
2 Correct 37 ms 2120 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1364 KB Output is correct
2 Correct 37 ms 2120 KB Output is correct
3 Correct 131 ms 13276 KB Output is correct
4 Correct 131 ms 13276 KB Output is correct
5 Correct 152 ms 13768 KB Output is correct
6 Correct 174 ms 14232 KB Output is correct
7 Correct 190 ms 14228 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 20 ms 1364 KB Output is correct
8 Correct 37 ms 2120 KB Output is correct
9 Correct 20 ms 1392 KB Output is correct
10 Correct 25 ms 2056 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 20 ms 1364 KB Output is correct
8 Correct 37 ms 2120 KB Output is correct
9 Correct 131 ms 13276 KB Output is correct
10 Correct 131 ms 13276 KB Output is correct
11 Correct 152 ms 13768 KB Output is correct
12 Correct 174 ms 14232 KB Output is correct
13 Correct 190 ms 14228 KB Output is correct
14 Correct 20 ms 1392 KB Output is correct
15 Correct 25 ms 2056 KB Output is correct
16 Correct 146 ms 13176 KB Output is correct
17 Correct 152 ms 13264 KB Output is correct
18 Correct 150 ms 13640 KB Output is correct
19 Correct 174 ms 14092 KB Output is correct
20 Correct 180 ms 14120 KB Output is correct