Submission #1111139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111139		fryingduc	Lucky Numbers (RMI19_lucky)	C++17	0 / 100	9 ms	4176 KiB

lucky

//#pragma GCC optimize("Ofast,unroll-loops") 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 2e5+5;
const int mod = 1e9+7;

int n, q;
string s;
int p[maxn];

void prec(){
    p[0] = 1, p[1] = 10; 
    for(int i = 2; i < maxn; ++i){
        p[i] = (p[i - 1] * 10 - p[i - 2] + mod * mod) % mod;
    }
}
struct Node{

    int val, ft, lt, both;
    int sz, check;
    int ft_pos, lt_pos;


    friend Node operator + (const Node &a, const Node &b){
            if(a.sz == 0) return b;
            if(b.sz == 0) return a;

           Node res;

           res.sz = a.sz + b.sz;
           res.ft_pos = a.ft_pos, res.lt_pos = b.lt_pos;
           if(a.lt_pos == 1 and b.ft_pos == 3) res.check = 0;
           else res.check = (a.check & b.check);

           bool gud = (a.check and a.ft_pos == 3);
           bool nice = (a.check and a.lt_pos == 1);

           res.val = (a.val - a.check) * p[b.sz] + (a.check ? b.val : 0);
           res.ft = (a.ft - gud) * p[b.sz] + (gud ? b.val : 0);
           res.lt = (a.val - a.check) * p[b.sz - 1] + (a.check ? b.lt : 0);
           res.both = (a.ft - gud) * p[b.sz - 1] + (gud ? b.lt : 0); 

           res.val -= ((a.lt - nice) * p[b.sz - 1] + (nice ? b.ft : 0));
           res.ft -= ((a.both - (gud and nice)) * p[b.sz - 1] + (gud and nice ? b.ft : 0));
           if(b.sz >= 2) res.lt -= ((a.lt - nice) * p[b.sz - 2] + (nice ? b.both : 0));
           if(b.sz >= 2) res.both -= ((a.both - (gud and nice)) * p[b.sz - 2] + (gud and nice ? b.both : 0));

           res.val = (res.val + mod * mod) % mod;
           res.ft = (res.ft + mod * mod) % mod;
           res.lt = (res.lt + mod * mod) % mod;
           res.both = (res.both + mod * mod) % mod;

           // debug(res.sz, res.ft_pos, res.lt_pos, res.val, res.ft, res.lt);

           return res;
    }
};

Node emp = {0, 0, 0, 0, 0, 0, 0, 0};
    
struct SegTree{
    int n;
    vector<Node> tree;
    void init(int sz){
        n = sz;
        tree.resize(n * 4 + 6, emp);
    }
    void build(int ind, int l, int r){
        if(l == r){
            int c = s[l] - '0' + 1;
            tree[ind] = Node({c, (c > 3), (c > 1), 0, 1, 1, c - 1, c - 1});
            return;
        }
        int mid = (l + r) / 2;
        build(ind * 2, l, mid);
        build(ind * 2 + 1, mid + 1, r);

        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];

        // debug(ind, l, r, tree[ind].val);
    }
    void update(int ind, int l, int r, int pos, int val){
        if(l == r){
            ++val;
            tree[ind] = Node({val, (val > 3), (val > 1), 0, 1, 1, val - 1, val - 1});
            return;
        }
        int mid = (l + r) / 2;
        if(l <= pos and pos <= mid) update(ind * 2, l, mid, pos, val);
        else update(ind * 2 + 1, mid + 1, r, pos, val);
        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
    }
    Node get(int ind, int l, int r, int x, int y){
        if(l > y || r < x) return emp;
        if(x <= l and r <= y) return tree[ind];
        int mid = (l + r) / 2;
        return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
    }
    void update(int pos, int val){
        update(1, 1, n, pos, val);
    }
    Node get(int x, int y){
        return get(1, 1, n, x, y);
    }
} st;

void solve(){

    prec();
    // debug(p[0], p[1], p[2], p[3]);


    cin >> n >> q;
    cin >> s;

    s = ' ' + s;

    st.init(n);
    st.build(1, 1, n);

    // debug(st.get(1, 2).val_tight, st.get(1, 1).val_tight);

    for(int i = 1; i <= q; ++i){
        int op, l, r; cin >> op >> l >> r;
        if(op == 1){
            cout << st.get(l, r).val << '\n';
        }
        else{
            st.update(l, r);
        }
    }

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

    int test = 1;
    // cin >> test;
    for(int i = 1; i <= test; i++){
      // cout << "Case " << "#" << i << ": "; 
      solve();
    }

    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";

    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