Submission #1121849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121849		Zero_OP	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	64 ms	20176 KiB

lucky

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

struct mint{
    int v;
    mint() : v(0) {}
    mint(int v) : v(v) {}

    mint& operator += (const mint& o){ v += o.v; if(v >= mod) v -= mod; return *this; }
    mint& operator -= (const mint& o){ v -= o.v; if(v < 0) v += mod; return *this; }
    mint& operator *= (const mint& o){ v = 1LL * v * o.v % mod; return *this; }

    friend mint operator + (mint a, const mint& b){ return a += b; }
    friend mint operator - (mint a, const mint& b){ return a -= b; }
    friend mint operator * (mint a, const mint& b){ return a *= b; }
};

struct info{ //[begin with 3][end with 1]
    mint n_smaller[2][2], n_equal[2][2], n_bigger[2][2];
    void make_info(int x){
        n_smaller[0][0] = x - (x > 1) - (x > 3);
        n_smaller[1][0] = (x > 3);
        n_smaller[0][1] = (x > 1);
        n_equal[0][0] = (x != 3) && (x != 1);
        n_equal[1][0] = (x == 3);
        n_equal[0][1] = (x == 1);
        n_bigger[0][0] = (9 - x) - (x < 1) - (x < 3);
        n_bigger[1][0] = x < 3;
        n_bigger[0][1] = x < 1;
    }

    friend info operator + (const info& a, const info& b){
        info c;
        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < 2; ++j){
                for(int k = 0; k < 2; ++k){
                    for(int l = 0; l < 2; ++l){
                        if(j && k) continue;
                        c.n_smaller[i][l] += a.n_equal[i][j] * (b.n_smaller[k][l]);
                        c.n_smaller[i][l] += a.n_smaller[i][j] * (b.n_smaller[k][l] + b.n_equal[k][l] + b.n_bigger[k][l]);
                        c.n_equal[i][l] += a.n_equal[i][j] * b.n_equal[k][l];
                        c.n_bigger[i][l] += a.n_equal[i][j] * b.n_bigger[k][l];
                        c.n_bigger[i][l] += a.n_bigger[i][j] * (b.n_smaller[k][l] + b.n_equal[k][l] + b.n_bigger[k][l]);
                    }
                }
            }
        }
        return c;
    }
};

struct segment_tree{
    vector<info> st;
    segment_tree(int n) : st(n << 2) {}

    void build(int id, int l, int r, const vector<int>& A){
        if(l == r) st[id].make_info(A[l]);
        else{
            int mid = l + r >> 1;
            build(id << 1, l, mid, A);
            build(id << 1 | 1, mid + 1, r, A);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    void update(int id, int l, int r, int pos, int val){
        if(l == r) st[id].make_info(val);
        else{
            int mid = l + r >> 1;
            if(pos <= mid) update(id << 1, l, mid, pos, val);
            else update(id << 1 | 1, mid + 1, r, pos, val);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    info query(int id, int l, int r, int u, int v){
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        if(u > mid) return query(id << 1 | 1, mid + 1, r, u, v);
        if(mid >= v) return query(id << 1, l, mid, u, v);
        return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
    }
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N, Q; string S;
    cin >> N >> Q >> S;
    vector<int> A(N);
    for(int i = 0; i < N; ++i){
        A[i] = S[i] - '0';
    }

    segment_tree tr(N);
    tr.build(1, 0, N - 1, A);

    auto solve = [&](int l, int r) -> int{
        info res = tr.query(1, 0, N - 1, l, r);
        mint ans = 0;
        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < 2; ++j){
                ans += res.n_smaller[i][j];
                ans += res.n_equal[i][j];
            }
        }
        return ans.v;
    };

    cout << solve(0, N - 1) << '\n';

    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int l, r;
            cin >> l >> r;
            --l, --r;
            cout << solve(l, r) << '\n';
        } else{
            int pos, val;
            cin >> pos >> val;
            --pos;
            tr.update(1, 0, N - 1, pos, val);
        }
    }

    return 0;
}

Compilation message (stderr)

lucky.cpp: In member function 'void segment_tree::build(int, int, int, const std::vector<int>&)':
lucky.cpp:62:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |             int mid = l + r >> 1;
      |                       ~~^~~
lucky.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
lucky.cpp:72:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |             int mid = l + r >> 1;
      |                       ~~^~~
lucky.cpp: In member function 'info segment_tree::query(int, int, int, int, int)':
lucky.cpp:81:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27