Submission #477548

#	Time	Username	Problem	Language	Result	Execution time	Memory
477548		Alexandruabcde	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	190 ms	14232 KiB

lucky

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27