oj.uz

Submission #856234

# Submission time Handle Problem Language Result Execution time Memory
856234 2023-10-02T20:42:24 Z divad Lucky Numbers (RMI19_lucky) C++14
100 / 100
 99 ms 17320 KB 
#include <bits/stdc++.h>
#define EQ 0
#define LE 1
#define state(x, y) x*2+y
#define typedig(x) (x == 1 ? 0 : 1 )
using namespace std;
const int MOD = 1e9+7;
const int NMAX = 1e5+2;
const int LAT = 2*2;
int n,q,t,l,r,pos,val;
int nr_loop;
string str;

struct Mat {
    int val[LAT][LAT] = {0};
    void reset(){
        memset(val, 0, sizeof(val));
    }

    void fill_diag(){
        for(int i = 0; i < LAT; i++){
            val[i][i] = 1;
        }
    }

    Mat operator * (const Mat &aux) const {
        Mat ans;
        for(int i = 0; i < LAT; i++){
            for(int j = 0; j < LAT; j++){
                for(int k = 0; k < LAT; k++){
                    ans.val[i][j] += (val[i][k] * 1ll * aux.val[k][j])%MOD;
                    ans.val[i][j] %= MOD;
                }
            }
        }
        return ans;
    }

};

struct Node {
    Mat dp;
    void init(int pos){
        dp.reset();
        for(int dig = 0; dig <= 9; dig++){
            for(int lst = 0; lst <= 1; lst++){
                if(lst == 0 && dig == 3){
                    continue;
                }
                if(dig == str[pos]-'0'){
                    dp.val[state(EQ, lst)][state(EQ, typedig(dig))]++;
                }
                if(dig < str[pos]-'0'){
                    dp.val[state(EQ, lst)][state(LE, typedig(dig))]++;
                }
                dp.val[state(LE, lst)][state(LE, typedig(dig))]++;
            }
        }
    }

    int eval(){
        int ans = 0;
        for(int i = 0; i <= 1; i++){
            ans += dp.val[0][state(LE, i)] + dp.val[0][state(EQ, i)];
            ans %= MOD;
        }
        return ans;
    }

    Node operator + (const Node &aux) const {
        Node ans;
        ans.dp = dp * aux.dp;
        return ans;
    }
} aint[4*NMAX];

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].init(st);
    }else{
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

Node query(int nod, int st, int dr, int l, int r){
    if(l <= st && dr <= r){
        return aint[nod];
    }else{
        int mid = (st+dr)/2;
        Node lson, rson;
        lson.dp.fill_diag();
        rson.dp.fill_diag();

        if(l <= mid){
            lson = query(2*nod, st, mid, l, r);
        }
        if(r >= mid+1){
            rson = query(2*nod+1, mid+1, dr, l, r);
        }

        return lson + rson;
    }
}

void update(int nod, int st, int dr, int pos){
    if(st == dr){
        aint[nod].init(st);
    }else{
        int mid = (st+dr)/2;
        if(pos <= mid){
            update(2*nod, st, mid, pos);
        }else{
            update(2*nod+1, mid+1, dr, pos);
        }
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

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

    Node aux;
    aux.dp.val[0][state(EQ, typedig(0))] = 1;

    cin >> n >> q;
    cin.ignore();
    getline(cin, str);
    str = "$"+str;
    build(1, 1, n);
    cout << (aux + aint[1]).eval() << "\n";
    while(q--){
        cin >> t;
        if(t == 1){
            cin >> l >> r;
            Node ans = query(1, 1, n, l, r);
            cout << (aux + ans).eval() << "\n";
        }else{
            cin >> pos >> val;
            str[pos] = (val+'0');
            update(1, 1, n, pos);
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2648 KB Output is correct
2 Correct 55 ms 2648 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2648 KB Output is correct
2 Correct 55 ms 2648 KB Output is correct
3 Correct 70 ms 17308 KB Output is correct
4 Correct 69 ms 17268 KB Output is correct
5 Correct 85 ms 17320 KB Output is correct
6 Correct 99 ms 17236 KB Output is correct
7 Correct 87 ms 17236 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 40 ms 2648 KB Output is correct
8 Correct 55 ms 2648 KB Output is correct
9 Correct 32 ms 2704 KB Output is correct
10 Correct 41 ms 2732 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 40 ms 2648 KB Output is correct
8 Correct 55 ms 2648 KB Output is correct
9 Correct 70 ms 17308 KB Output is correct
10 Correct 69 ms 17268 KB Output is correct
11 Correct 85 ms 17320 KB Output is correct
12 Correct 99 ms 17236 KB Output is correct
13 Correct 87 ms 17236 KB Output is correct
14 Correct 32 ms 2704 KB Output is correct
15 Correct 41 ms 2732 KB Output is correct
16 Correct 62 ms 17240 KB Output is correct
17 Correct 59 ms 17260 KB Output is correct
18 Correct 67 ms 17236 KB Output is correct
19 Correct 74 ms 17240 KB Output is correct
20 Correct 78 ms 17264 KB Output is correct