Submission #685078

#	Time	Username	Problem	Language	Result	Execution time	Memory
685078		nifeshe	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	120 ms	47616 KiB

lucky

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#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 mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

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; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 1e9 + 7;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e5 + 1;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void add(int &a, int b) {
    a += b;
    if(a >= mod) a -= mod;
}

struct node {
    int l = 0;
    ///[first == 3][lst == 1][flag]
    vector<array<array<int, 2>, 2>> dp;

    node() {
        dp.resize(2, {(array<int, 2>){0, 0}, (array<int, 2>){0, 0}});
    }
};

vector<array<array<int, 2>, 2>> precalc(MAX);

node combine(const node &a, const node &b) {
    if(!a.l) return b;
    if(!b.l) return a;
    node res;
    res.l = a.l + b.l;
    int L = b.l;
    for(int fa : {0, 1}) {
        for(int lsta : {0, 1}) {
            for(int fb : {0, 1}) {
                for(int lstb : {0, 1}) {
                    if(lsta && fb) continue;
                    add(res.dp[fa][lstb][0], a.dp[fa][lsta][0] * precalc[L][fb][lstb] % mod);
                    add(res.dp[fa][lstb][0], a.dp[fa][lsta][1] * b.dp[fb][lstb][0] % mod);
                    add(res.dp[fa][lstb][1], a.dp[fa][lsta][1] * b.dp[fb][lstb][1] % mod);
                }
            }
        }
    }
//    for(int f : {0, 1}) for(int lst : {0, 1}) cout << res.dp[f][lst][0] << " " << res.dp[f][lst][1] << " ";
//    cout << endl;
    return res;
}

int n;
node ntrl;
vector<node> t;

void build(string &s, int v = 0, int l = 0, int r = n) {
    if(r - l == 1) {
        t[v].l = 1;
        int x = s[l] - '0';
        for(int i = 0; i < x; i++) add(t[v].dp[i == 3][i == 1][0], 1);
        add(t[v].dp[x == 3][x == 1][1], 1);
        return;
    }
    int m = (l + r) / 2;
    build(s, 2 * v + 1, l, m);
    build(s, 2 * v + 2, m, r);
    t[v] = combine(t[2 * v + 1], t[2 * v + 2]);
}

void update(int i, int x, int v = 0, int l = 0, int r = n) {
    if(r - l == 1) {
        t[v] = ntrl;
        t[v].l = 1;
        for(int i = 0; i < x; i++) add(t[v].dp[i == 3][i == 1][0], 1);
        add(t[v].dp[x == 3][x == 1][1], 1);
        return;
    }
    int m = (l + r) / 2;
    if(i < m) update(i, x, 2 * v + 1, l, m);
    else update(i, x, 2 * v + 2, m, r);
    t[v] = combine(t[2 * v + 1], t[2 * v + 2]);
}

node get(int l, int r, int v = 0, int tl = 0, int tr = n) {
    if(r <= tl || tr <= l) return ntrl;
    if(l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return combine(get(l, r, 2 * v + 1, tl, tm), get(l, r, 2 * v + 2, tm, tr));
}

int get_ans(const node &v) {
    int ans = 0;
    for(int f : {0, 1}) {
        for(int lst : {0, 1}) {
            add(ans, v.dp[f][lst][0]);
            add(ans, v.dp[f][lst][1]);
        }
    }
    return ans;
}

void solve() {
    int q;
    cin >> n >> q;
    t.resize(4 * n + 5, ntrl);
    string s; cin >> s;
    build(s);
    cout << get_ans(t[0]) << '\n';
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int l, r;
            cin >> l >> r; l--;
            cout << get_ans(get(l, r)) << '\n';
        }
        else {
            int i, x;
            cin >> i >> x; i--;
            update(i, x);
        }
    }
}

/*
6 1
466461
1 2 6
*/

signed main() {
    for(int i = 0; i < 10; i++) add(precalc[1][i == 3][i == 1], 1);
    for(int i = 2; i < MAX; i++) {
        for(int j = 0; j < 10; j++) {
            for(int f : {0, 1}) {
                for(int lst : {0, 1}) {
                    if(lst && j == 3) continue;
                    add(precalc[i][f][j == 1], precalc[i - 1][f][lst]);
                }
            }
        }
    }
//    for(int i = 2; i < 3; i++) {
//        for(int f : {0, 1}) {
//            for(int lst : {0, 1}) {
//                cout << precalc[i][f][lst] << " ";
//            }
//        }
//        cout << endl;
//    }
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

lucky.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

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