oj.uz

Submission #1111145

# Submission time Handle Problem Language Result Execution time Memory
1111145 2024-11-11T15:19:28 Z fryingduc Lucky Numbers (RMI19_lucky) C++17
100 / 100
 34 ms 27548 KB 
//#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);
    
    cout << st.get(1, n).val << '\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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1928 KB Output is correct
4 Correct 3 ms 1968 KB Output is correct
5 Correct 3 ms 1872 KB Output is correct
6 Correct 3 ms 1872 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3920 KB Output is correct
2 Correct 12 ms 4688 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3920 KB Output is correct
2 Correct 12 ms 4688 KB Output is correct
3 Correct 24 ms 22348 KB Output is correct
4 Correct 27 ms 22488 KB Output is correct
5 Correct 23 ms 24908 KB Output is correct
6 Correct 28 ms 27468 KB Output is correct
7 Correct 33 ms 27524 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1928 KB Output is correct
4 Correct 3 ms 1968 KB Output is correct
5 Correct 3 ms 1872 KB Output is correct
6 Correct 3 ms 1872 KB Output is correct
7 Correct 10 ms 3920 KB Output is correct
8 Correct 12 ms 4688 KB Output is correct
9 Correct 11 ms 4176 KB Output is correct
10 Correct 10 ms 4856 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1928 KB Output is correct
4 Correct 3 ms 1968 KB Output is correct
5 Correct 3 ms 1872 KB Output is correct
6 Correct 3 ms 1872 KB Output is correct
7 Correct 10 ms 3920 KB Output is correct
8 Correct 12 ms 4688 KB Output is correct
9 Correct 24 ms 22348 KB Output is correct
10 Correct 27 ms 22488 KB Output is correct
11 Correct 23 ms 24908 KB Output is correct
12 Correct 28 ms 27468 KB Output is correct
13 Correct 33 ms 27524 KB Output is correct
14 Correct 11 ms 4176 KB Output is correct
15 Correct 10 ms 4856 KB Output is correct
16 Correct 26 ms 22384 KB Output is correct
17 Correct 18 ms 22456 KB Output is correct
18 Correct 25 ms 24992 KB Output is correct
19 Correct 34 ms 27468 KB Output is correct
20 Correct 24 ms 27548 KB Output is correct