oj.uz

Submission #856233

# Submission time Handle Problem Language Result Execution time Memory
856233 2023-10-02T20:41:08 Z divad Lucky Numbers (RMI19_lucky) C++14
100 / 100
 81 ms 17496 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops,fast-math")
#pragma GCC target("avx2")
#define EQ 0
#define LE 1
#define state(x, y) x*2+y
#define typedig(x) (x == 1 ? 0 : (x == 3 ? 1 : 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;

ifstream fin("test.in");
ofstream fout("test.out");

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);
#ifdef ONPC
    #define cin fin
    #define cout fout
#endif // ONPC
    cin.tie(nullptr);
    cout.tie(nullptr);

    Node aux;
    aux.dp.val[0][state(EQ, 1)] = 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 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 356 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 36 ms 2676 KB Output is correct
2 Correct 43 ms 2652 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2676 KB Output is correct
2 Correct 43 ms 2652 KB Output is correct
3 Correct 58 ms 17240 KB Output is correct
4 Correct 59 ms 17248 KB Output is correct
5 Correct 66 ms 17236 KB Output is correct
6 Correct 81 ms 17492 KB Output is correct
7 Correct 77 ms 17404 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 36 ms 2676 KB Output is correct
8 Correct 43 ms 2652 KB Output is correct
9 Correct 26 ms 2648 KB Output is correct
10 Correct 41 ms 2652 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 36 ms 2676 KB Output is correct
8 Correct 43 ms 2652 KB Output is correct
9 Correct 58 ms 17240 KB Output is correct
10 Correct 59 ms 17248 KB Output is correct
11 Correct 66 ms 17236 KB Output is correct
12 Correct 81 ms 17492 KB Output is correct
13 Correct 77 ms 17404 KB Output is correct
14 Correct 26 ms 2648 KB Output is correct
15 Correct 41 ms 2652 KB Output is correct
16 Correct 50 ms 17424 KB Output is correct
17 Correct 48 ms 17440 KB Output is correct
18 Correct 56 ms 17228 KB Output is correct
19 Correct 61 ms 17492 KB Output is correct
20 Correct 69 ms 17496 KB Output is correct