oj.uz

Submission #498197

# Submission time Handle Problem Language Result Execution time Memory
498197 2021-12-24T15:20:59 Z couplefire Lucky Numbers (RMI19_lucky) C++17
100 / 100
 86 ms 17680 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1<<17;
const int MOD = 1000000007;

int add(int a, int b){return a+b>=MOD?a+b-MOD:a+b;}
void inc(int& a, int b){a=add(a, b);}
int sub(int a, int b){return a-b<0?a-b+MOD:a-b;}
void dec(int& a, int b){a=sub(a, b);}
int mul(int a, int b){return 1ll*a*b%MOD;}
void grow(int& a, int b){a=mul(a, b);}

int n, q, arr[N], dp[N<<1][4][4];

void init(int pos, int res[4][4]){
    for(int i = 0; i<4; ++i){
        for(int j = 0; j<4; ++j)
            res[i][j] = 0;
        bool eq = i/2;
        bool one = i%2;
        for(int k = 0; k<=(eq?arr[pos]:9); ++k){
            if(one && k==3) continue;
            inc(res[i][(eq&&k==arr[pos])*2+(k==1)], 1);
        }
    }
}

void comb(int a[4][4], int b[4][4], int res[4][4]){
    for(int i = 0; i<4; ++i)
        for(int j = 0; j<4; ++j){
            res[i][j] = 0;
            inc(res[i][j], mul(a[i][0], b[0][j]));
            inc(res[i][j], mul(a[i][1], b[1][j]));
            inc(res[i][j], mul(a[i][2], b[2][j]));
            inc(res[i][j], mul(a[i][3], b[3][j]));
        }
}

void build(int v, int tl, int tr){
    if(tl==tr) return init(tl, dp[v]);
    int tm = (tl+tr)>>1;
    build(v<<1, tl, tm); build(v<<1|1, tm+1, tr);
    comb(dp[v<<1], dp[v<<1|1], dp[v]);
}

void upd(int pos, int val, int v, int tl, int tr){
    if(tl==tr){arr[pos] = val; return init(tl, dp[v]);}
    int tm = (tl+tr)>>1;
    if(pos<=tm) upd(pos, val, v<<1, tl, tm);
    else upd(pos, val, v<<1|1, tm+1, tr);
    comb(dp[v<<1], dp[v<<1|1], dp[v]);
}

void query(int l, int r, int res[4][4], int v, int tl, int tr){
    if(l<=tl && tr<=r){
        for(int i = 0; i<4; ++i)
            for(int j = 0; j<4; ++j)
                res[i][j] = dp[v][i][j];
        return;
    }
    int tm = (tl+tr)>>1;
    if(r<=tm) query(l, r, res, v<<1, tl, tm);
    else if(l>tm) query(l, r, res, v<<1|1, tm+1, tr);
    else{
        int ll[4][4], rr[4][4];
        query(l, r, ll, v<<1, tl, tm);
        query(l, r, rr, v<<1|1, tm+1, tr);
        comb(ll, rr, res);
    }
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q; string s; cin >> s;
    for(int i = 1; i<=n; ++i)
        arr[i] = s[i-1]-'0';
    build(1, 1, n);
    for(int i = 0; i<=q; ++i){
        int t, x, y;
        if(!i) t = 1, x = 1, y = n;
        else cin >> t >> x >> y;
        if(t==1){
            int res[4][4];
            query(x, y, res, 1, 1, n);
            cout << add(add(res[2][0], res[2][1]), add(res[2][2], res[2][3])) << '\n';
        } else upd(x, y, 1, 1, n);
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1440 KB Output is correct
2 Correct 30 ms 2616 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1440 KB Output is correct
2 Correct 30 ms 2616 KB Output is correct
3 Correct 71 ms 17428 KB Output is correct
4 Correct 61 ms 17424 KB Output is correct
5 Correct 65 ms 17500 KB Output is correct
6 Correct 66 ms 17612 KB Output is correct
7 Correct 75 ms 17644 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 21 ms 1440 KB Output is correct
8 Correct 30 ms 2616 KB Output is correct
9 Correct 29 ms 1488 KB Output is correct
10 Correct 43 ms 2560 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 21 ms 1440 KB Output is correct
8 Correct 30 ms 2616 KB Output is correct
9 Correct 71 ms 17428 KB Output is correct
10 Correct 61 ms 17424 KB Output is correct
11 Correct 65 ms 17500 KB Output is correct
12 Correct 66 ms 17612 KB Output is correct
13 Correct 75 ms 17644 KB Output is correct
14 Correct 29 ms 1488 KB Output is correct
15 Correct 43 ms 2560 KB Output is correct
16 Correct 59 ms 17416 KB Output is correct
17 Correct 55 ms 17428 KB Output is correct
18 Correct 67 ms 17464 KB Output is correct
19 Correct 86 ms 17480 KB Output is correct
20 Correct 78 ms 17680 KB Output is correct