Submission #854404

#	Time	Username	Problem	Language	Result	Execution time	Memory
854404		lolismek	Lucky Numbers (RMI19_lucky)	C++14	0 / 100	40 ms	38232 KiB

lucky

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 27
• Subtask 5: 0 / 9
• Subtask 6: 0 / 27