oj.uz

Submission #854406

# Submission time Handle Problem Language Result Execution time Memory
854406 2023-09-27T10:15:11 Z lolismek Lucky Numbers (RMI19_lucky) C++14
100 / 100
 79 ms 38520 KB 
#include <iostream>

#define int long long

using namespace std;

const int NMAX = 1e5;
const int MOD = 1e9 + 7;

int v[NMAX + 1];

struct Node{
    int s[2][2];
    int e[2][2];
    int b[2][2];

    Node(){
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                s[i][j] = e[i][j] = b[i][j] = 0;
            }
        }
    }
}seg[4 * NMAX + 1];

Node merge(Node L, Node R){
    Node aux;

    for(int i1 = 0; i1 < 2; i1++){
        for(int i2 = 0; i2 < 2; i2++){
            for(int i3 = 0; i3 < 2; i3++){
                for(int i4 = 0; i4 < 2; i4++){
                    if(i2 == 1 && i3 == 1){
                        continue;
                    }
                    (aux.s[i1][i4] += (1ll * L.s[i1][i2] * R.s[i3][i4])) %= MOD;
                    (aux.s[i1][i4] += (1ll * L.s[i1][i2] * R.e[i3][i4])) %= MOD;
                    (aux.s[i1][i4] += (1ll * L.s[i1][i2] * R.b[i3][i4])) %= MOD;
                    (aux.s[i1][i4] += (1ll * L.e[i1][i2] * R.s[i3][i4])) %= MOD;

                    (aux.e[i1][i4] += (1ll * L.e[i1][i2] * R.e[i3][i4])) %= MOD;

                    (aux.b[i1][i4] += (1ll * L.b[i1][i2] * R.s[i3][i4])) %= MOD;
                    (aux.b[i1][i4] += (1ll * L.b[i1][i2] * R.b[i3][i4])) %= MOD;
                    (aux.b[i1][i4] += (1ll * L.e[i1][i2] * R.b[i3][i4])) %= MOD;
                    (aux.b[i1][i4] += (1ll * L.b[i1][i2] * R.e[i3][i4])) %= MOD;
                }
            }
        }
    }

    return aux;
}

Node cr(int cif){
    Node aux;
    for(int i = 0; i <= 9; i++){
        if(i < cif){
            if(i == 1){
                aux.s[0][1] += 1;
            }else if(i == 3){
                aux.s[1][0] += 1;
            }else{
                aux.s[0][0] += 1;
            }
        }else if(i == cif){
            if(i == 1){
                aux.e[0][1] += 1;
            }else if(i == 3){
                aux.e[1][0] += 1;
            }else{
                aux.e[0][0] += 1;
            }
        }else{
            if(i == 1){
                aux.b[0][1] += 1;
            }else if(i == 3){
                aux.b[1][0] += 1;
            }else{
                aux.b[0][0] += 1;
            }
        }
    }
    return aux;
}

string s;
void build(int node, int left, int right){
    if(left == right){
        int cif = s[left - 1] - '0';
        seg[node] = cr(cif);
        return;
    }

    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);

    seg[node] = merge(seg[2 * node], seg[2 * node + 1]);
}

void update(int node, int left, int right, int pos, int val){
    if(left == right){
        seg[node] = cr(val);
        return;
    }

    int mid = (left + right) / 2;
    if(pos <= mid){
        update(2 * node, left, mid, pos, val);
    }else{
        update(2 * node + 1, mid + 1, right, pos, val);
    }

    seg[node] = merge(seg[2 * node], seg[2 * node + 1]);
}

Node query(int node, int left, int right, int ql, int qr){
    if(ql <= left && right <= qr){
        return seg[node];
    }

    int mid = (left + right) / 2;

    Node ans;
    bool ok = false;
    if(ql <= mid){
        ok = true;
        ans = query(2 * node, left, mid, ql, qr);
    }
    if(mid + 1 <= qr){
        if(ok){
            ans = merge(ans, query(2 * node + 1, mid + 1, right, ql, qr));
        }else{
            ans = query(2 * node + 1, mid + 1, right, ql, qr);
        }
    }

    return ans;
}

signed main(){

    int n, q;
    cin >> n >> q;

    cin >> s;

    build(1, 1, n);

    int init = 0;
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            (init += seg[1].s[i][j]) %= MOD;
            (init += seg[1].e[i][j]) %= MOD;
        }
    }

    cout << init << '\n';

    while(q--){
        int type;
        cin >> type;

        if(type == 1){
            int l, r;
            cin >> l >> r;
            Node x = query(1, 1, n, l, r);
            int ans = 0;
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 2; j++){
                    (ans += x.s[i][j]) %= MOD;
                    (ans += x.e[i][j]) %= MOD;
                }
            }
            cout << ans << '\n';
        }else{
            int pos, val;
            cin >> pos >> val;
            update(1, 1, n, pos, val);
        }
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37980 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 6 ms 37776 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37980 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 6 ms 37776 KB Output is correct
4 Correct 6 ms 37976 KB Output is correct
5 Correct 7 ms 38016 KB Output is correct
6 Correct 6 ms 37976 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37980 KB Output is correct
2 Correct 48 ms 38176 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37980 KB Output is correct
2 Correct 48 ms 38176 KB Output is correct
3 Correct 65 ms 38232 KB Output is correct
4 Correct 68 ms 38232 KB Output is correct
5 Correct 74 ms 38480 KB Output is correct
6 Correct 79 ms 38520 KB Output is correct
7 Correct 79 ms 38480 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37980 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 6 ms 37776 KB Output is correct
4 Correct 6 ms 37976 KB Output is correct
5 Correct 7 ms 38016 KB Output is correct
6 Correct 6 ms 37976 KB Output is correct
7 Correct 39 ms 37980 KB Output is correct
8 Correct 48 ms 38176 KB Output is correct
9 Correct 35 ms 37980 KB Output is correct
10 Correct 44 ms 38164 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37980 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 6 ms 37776 KB Output is correct
4 Correct 6 ms 37976 KB Output is correct
5 Correct 7 ms 38016 KB Output is correct
6 Correct 6 ms 37976 KB Output is correct
7 Correct 39 ms 37980 KB Output is correct
8 Correct 48 ms 38176 KB Output is correct
9 Correct 65 ms 38232 KB Output is correct
10 Correct 68 ms 38232 KB Output is correct
11 Correct 74 ms 38480 KB Output is correct
12 Correct 79 ms 38520 KB Output is correct
13 Correct 79 ms 38480 KB Output is correct
14 Correct 35 ms 37980 KB Output is correct
15 Correct 44 ms 38164 KB Output is correct
16 Correct 73 ms 38492 KB Output is correct
17 Correct 62 ms 38236 KB Output is correct
18 Correct 68 ms 38232 KB Output is correct
19 Correct 76 ms 38452 KB Output is correct
20 Correct 78 ms 38428 KB Output is correct