Submission #685064

#	Time	Username	Problem	Language	Result	Execution time	Memory
685064		KiriLL1ca	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	92 ms	21260 KiB

lucky

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
#define pb push_back
#define fr first
#define sc second
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
inline int add (int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
inline int mul (int a, int b) { return (a * 1ll * b) % mod; }

#pragma GCC optimize ("Ofast")

struct segtree {
    struct node {
        int sm[2][2], eq[2][2], la[2][2];
        bool orz;
        node () {
            orz = 1;
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    sm[i][j] = eq[i][j] = la[i][j] = 0;
                }
            }
        }
        node (int x) {
            sm[0][0] = x - (x > 1) - (x > 3);
            sm[0][1] = (x > 1);
            sm[1][0] = (x > 3);
            sm[1][1] = 0;

            eq[0][0] = (!(x == 1) && !(x == 3)) ;
            eq[0][1] = (x == 1);
            eq[1][0] = (x == 3);
            eq[1][1] = 0;

            la[0][0] = 9 - x - (x < 1) - (x < 3);
            la[0][1] = (x < 1);
            la[1][0] = (x < 3);
            la[1][1] = 0;

            orz = 0;
        }

        inline node operator + (const node &b) const {
            node res;
            if (orz) return b;
            if (b.orz) return *this;
            res.orz = 0;
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    for (int e1 = 0; e1 < 2; ++e1) {
                        for (int b3 = 0; b3 < 2; ++b3) {
                            if (e1 && b3) continue;
                            res.sm[i][j] = add(res.sm[i][j], mul(sm[i][e1], b.sm[b3][j]));
                            res.sm[i][j] = add(res.sm[i][j], mul(sm[i][e1], b.eq[b3][j]));
                            res.sm[i][j] = add(res.sm[i][j], mul(sm[i][e1], b.la[b3][j]));
                            res.sm[i][j] = add(res.sm[i][j], mul(eq[i][e1], b.sm[b3][j]));

                            res.eq[i][j] = add(res.eq[i][j], mul(eq[i][e1], b.eq[b3][j]));

                            res.la[i][j] = add(res.la[i][j], mul(eq[i][e1], b.la[b3][j]));
                            res.la[i][j] = add(res.la[i][j], mul(la[i][e1], b.sm[b3][j]));
                            res.la[i][j] = add(res.la[i][j], mul(la[i][e1], b.eq[b3][j]));
                            res.la[i][j] = add(res.la[i][j], mul(la[i][e1], b.la[b3][j]));
                        }
                    }
                }
            }
            return res;
        }
    };

    int n; vector <node> t;
    segtree (const string &s) : n(sz(s)), t(4 * sz(s)) { build(1, 0, n - 1, s); }

    inline void build (int v, int tl, int tr, const string &s) {
        if (tl == tr) return void(t[v] = node(s[tl] - '0'));
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm, s); build(v << 1 | 1, tm + 1, tr, s);
        t[v] = t[v << 1] + t[v << 1 | 1];
    }
    inline void upd (int v, int tl, int tr, int pos, int x) {
        if (tl == tr) return void(t[v] = node(x));
        int tm = (tl + tr) >> 1;
        if (pos <= tm) upd(v << 1, tl, tm, pos, x);
        else upd(v << 1 | 1, tm + 1, tr, pos, x);
        t[v] = t[v << 1] + t[v << 1 | 1];
    }
    inline node get (int v, int tl, int tr, int l, int r) {
        if (l > tr || tl > r) return node();
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(v << 1, tl, tm, l, r) + get(v << 1 | 1, tm + 1, tr, l, r);
    }

    inline void upd (int pos, int x) { upd(1, 0, n - 1, pos, x); }
    inline int get (int l, int r) {
        node a = get(1, 0, n - 1, l, r);
        int res = 0;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                res = add(res, a.sm[i][j]);
                res = add(res, a.eq[i][j]);
            }
        }
        return res;
    }
};

inline void solve () {
    int n, q; cin >> n >> q;
    string s; cin >> s;
    segtree st (s);
    cout << st.get(0, n - 1) << endl;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int l, r; cin >> l >> r; --l, --r;
            cout << st.get(l, r) << endl;
        }
        else {
            int i, x; cin >> i >> x; --i;
            st.upd(i, x);
        }
    }
}

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

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int t = 1; // cin >> t;
    while (t--) solve();
    return 0;
}

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