oj.uz

Submission #494240

# Submission time Handle Problem Language Result Execution time Memory
494240 2021-12-14T21:55:22 Z Bliznetc Lucky Numbers (RMI19_lucky) C++17
46 / 100
 200 ms 85856 KB 
#include <bits/stdc++.h>

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;
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 (a * b) % 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 (node a) {
    int cur = 0;
    for (int f = 0; f < 2; f++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cur += a.dp[i][j][f];
                cur %= mod;
            }
        }
    }
    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(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(ans) << "\n";
        }
        else {
            int pos, x;
            cin >> pos >> x;
            a[pos] = x;
            upd(1, 1, n, pos, x);
        }
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84940 KB Output is correct
2 Correct 32 ms 84828 KB Output is correct
3 Correct 34 ms 84804 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84940 KB Output is correct
2 Correct 32 ms 84828 KB Output is correct
3 Correct 34 ms 84804 KB Output is correct
4 Correct 35 ms 84832 KB Output is correct
5 Correct 33 ms 84804 KB Output is correct
6 Correct 34 ms 84940 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 85048 KB Output is correct
2 Correct 166 ms 85136 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 85048 KB Output is correct
2 Correct 166 ms 85136 KB Output is correct
3 Execution timed out 281 ms 85856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84940 KB Output is correct
2 Correct 32 ms 84828 KB Output is correct
3 Correct 34 ms 84804 KB Output is correct
4 Correct 35 ms 84832 KB Output is correct
5 Correct 33 ms 84804 KB Output is correct
6 Correct 34 ms 84940 KB Output is correct
7 Correct 141 ms 85048 KB Output is correct
8 Correct 166 ms 85136 KB Output is correct
9 Correct 158 ms 85120 KB Output is correct
10 Correct 190 ms 85156 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84940 KB Output is correct
2 Correct 32 ms 84828 KB Output is correct
3 Correct 34 ms 84804 KB Output is correct
4 Correct 35 ms 84832 KB Output is correct
5 Correct 33 ms 84804 KB Output is correct
6 Correct 34 ms 84940 KB Output is correct
7 Correct 141 ms 85048 KB Output is correct
8 Correct 166 ms 85136 KB Output is correct
9 Execution timed out 281 ms 85856 KB Time limit exceeded
10 Halted 0 ms 0 KB -