oj.uz

Submission #685064

# Submission time Handle Problem Language Result Execution time Memory
685064 2023-01-23T08:35:30 Z KiriLL1ca Lucky Numbers (RMI19_lucky) C++17
100 / 100
 92 ms 21260 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2140 KB Output is correct
2 Correct 49 ms 2640 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2140 KB Output is correct
2 Correct 49 ms 2640 KB Output is correct
3 Correct 78 ms 17028 KB Output is correct
4 Correct 78 ms 17008 KB Output is correct
5 Correct 79 ms 19156 KB Output is correct
6 Correct 89 ms 21180 KB Output is correct
7 Correct 92 ms 21260 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 38 ms 2140 KB Output is correct
8 Correct 49 ms 2640 KB Output is correct
9 Correct 34 ms 1996 KB Output is correct
10 Correct 44 ms 2516 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 38 ms 2140 KB Output is correct
8 Correct 49 ms 2640 KB Output is correct
9 Correct 78 ms 17028 KB Output is correct
10 Correct 78 ms 17008 KB Output is correct
11 Correct 79 ms 19156 KB Output is correct
12 Correct 89 ms 21180 KB Output is correct
13 Correct 92 ms 21260 KB Output is correct
14 Correct 34 ms 1996 KB Output is correct
15 Correct 44 ms 2516 KB Output is correct
16 Correct 79 ms 16996 KB Output is correct
17 Correct 79 ms 17104 KB Output is correct
18 Correct 78 ms 19036 KB Output is correct
19 Correct 84 ms 21136 KB Output is correct
20 Correct 86 ms 21100 KB Output is correct