Submission #494259

#	Time	Username	Problem	Language	Result	Execution time	Memory
494259		Bliznetc	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	187 ms	43232 KiB

lucky

#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
//#define int long long

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

const int N = 100100;
const int mod = 1e9 + 7;
int a[N];

int num (int x) {
    if (x == 1) {
        return 0;
    }
    if (x == 3) {
        return 1;
    }
    return 2;
}

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


int mult (int a, int b) {
    return (long long)a * b *1ll % mod;
}


struct node {
    int dp[3][3][3];
    node() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int f = 0; f < 3; f++) {
                    dp[i][j][f] = 0;
                }
            }
        }
    }
};

node t[4 * N];

void _clear(node &a) {
    for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
            for (int i1 = 0; i1 <= 2; i1++)
                a.dp[i][j][i1] = 0;
}

int sum1[3][3], sum2[3][3];

node recalc (node a, node b) {
    node c;
    for (int f = 0; f <= 2; f++) {
        for (int d = 0; d <= 2; d++) {
            sum1[d][f] = sum2[d][f] = 0;
            for (int j = 0; j <= 2; j++) {
                add(sum1[d][f], a.dp[d][j][f]);
                add(sum2[d][f], b.dp[j][d][f]);
            }
        }
    }

    for (int f = 0; f <= 2; f++) {
        for (int s = 0; s <= 2; s++) {
            for (int d1 = 0; d1 <= 2; d1++) {
                for (int d2 = 0; d2 <= 2; d2++) {
                    int nf = (f != 1 ? f : s);
                    add(c.dp[d1][d2][nf], mult(sum1[d1][f], sum2[d2][s]));
                    add(c.dp[d1][d2][nf], -mult(a.dp[d1][0][f], b.dp[1][d2][s]));
                }
            }
        }
    }
    return c;
}

void build (int v, int l, int r) {
    if (l == r) {
        for (int i = 0; i <= 9; i++) {
            int f = (a[l] < i ? 2 : a[l] == i);
            add(t[v].dp[num(i)][num(i)][f], 1);
        }
        return;
    }
    int mid = (r + l) / 2;
    build(2 * v, l, mid);
    build(2 * v + 1, mid + 1, r);
    t[v] = recalc(t[2 * v], t[2 * v + 1]);
}


void upd (int v, int l, int r, int pos, int val) {
    if (l > pos || r < pos) {
        return;
    }
    if (l == r) {
        _clear(t[v]);
        for (int i = 0; i <= 9; i++) {
            int f = (i > a[l] ? 2 : a[l] == i);
            add(t[v].dp[num(i)][num(i)][f], 1);
        }
        return;
    }
    int mid = (r + l) / 2;
    upd (2 * v, l, mid, pos, val);
    upd (2 * v + 1, mid + 1, r, pos, val);
    t[v] = recalc(t[2 * v], t[2 * v + 1]);
}

node ans;
int used;

void get (int v, int l, int r, int tl, int tr) {
    if (l > tr || r < tl) {
        return;
    }
    if (l >= tl && r <= tr) {
        if (!used) {
            ans = t[v];
        }
        else {
            ans = recalc(ans, t[v]);
        }
        used = 1;
        return;
    }

    int mid = (l + r) / 2;
    get (2 * v, l, mid, tl, tr);
    get (2 * v + 1, mid + 1, r, tl, tr);
}

int calc_ans () {
    int cur = 0;
    for (int f = 0; f < 2; f++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                add(cur, ans.dp[i][j][f]);
            }
        }
    }
    return cur;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }

    build (1, 1, n);

    get(1, 1, n, 1, n);
    cout << calc_ans() << "\n";

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            used = 0;
            _clear(ans);
            get(1, 1, n, l, r);
            cout << calc_ans() << "\n";
        }
        else {
            int pos, x;
            cin >> pos >> x;
            a[pos] = x;
            upd(1, 1, n, pos, x);
        }
    }
}

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