oj.uz

Submission #685078

# Submission time Handle Problem Language Result Execution time Memory
685078 2023-01-23T09:34:04 Z nifeshe Lucky Numbers (RMI19_lucky) C++17
100 / 100
 120 ms 47616 KB 
#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3412 KB Output is correct
2 Correct 13 ms 3440 KB Output is correct
3 Correct 11 ms 3440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3412 KB Output is correct
2 Correct 13 ms 3440 KB Output is correct
3 Correct 11 ms 3440 KB Output is correct
4 Correct 12 ms 3444 KB Output is correct
5 Correct 10 ms 3432 KB Output is correct
6 Correct 11 ms 3444 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7028 KB Output is correct
2 Correct 49 ms 8036 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7028 KB Output is correct
2 Correct 49 ms 8036 KB Output is correct
3 Correct 92 ms 38804 KB Output is correct
4 Correct 90 ms 38760 KB Output is correct
5 Correct 97 ms 43092 KB Output is correct
6 Correct 105 ms 47600 KB Output is correct
7 Correct 111 ms 47616 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3412 KB Output is correct
2 Correct 13 ms 3440 KB Output is correct
3 Correct 11 ms 3440 KB Output is correct
4 Correct 12 ms 3444 KB Output is correct
5 Correct 10 ms 3432 KB Output is correct
6 Correct 11 ms 3444 KB Output is correct
7 Correct 41 ms 7028 KB Output is correct
8 Correct 49 ms 8036 KB Output is correct
9 Correct 37 ms 6992 KB Output is correct
10 Correct 45 ms 7924 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3412 KB Output is correct
2 Correct 13 ms 3440 KB Output is correct
3 Correct 11 ms 3440 KB Output is correct
4 Correct 12 ms 3444 KB Output is correct
5 Correct 10 ms 3432 KB Output is correct
6 Correct 11 ms 3444 KB Output is correct
7 Correct 41 ms 7028 KB Output is correct
8 Correct 49 ms 8036 KB Output is correct
9 Correct 92 ms 38804 KB Output is correct
10 Correct 90 ms 38760 KB Output is correct
11 Correct 97 ms 43092 KB Output is correct
12 Correct 105 ms 47600 KB Output is correct
13 Correct 111 ms 47616 KB Output is correct
14 Correct 37 ms 6992 KB Output is correct
15 Correct 45 ms 7924 KB Output is correct
16 Correct 91 ms 38724 KB Output is correct
17 Correct 89 ms 38772 KB Output is correct
18 Correct 97 ms 43104 KB Output is correct
19 Correct 120 ms 47456 KB Output is correct
20 Correct 101 ms 47524 KB Output is correct