oj.uz

Submission #854404

# Submission time Handle Problem Language Result Execution time Memory
854404 2023-09-27T10:07:22 Z lolismek Lucky Numbers (RMI19_lucky) C++14
0 / 100
 40 ms 38232 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);

    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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 38232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 38232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 38056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 38056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 38232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 38232 KB Output isn't correct
2 Halted 0 ms 0 KB -