oj.uz

Submission #494258

# Submission time Handle Problem Language Result Execution time Memory
494258 2021-12-14T22:01:41 Z Bliznetc Lucky Numbers (RMI19_lucky) C++17
46 / 100
 200 ms 43292 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;
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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42612 KB Output is correct
2 Correct 19 ms 42628 KB Output is correct
3 Correct 20 ms 42620 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42612 KB Output is correct
2 Correct 19 ms 42628 KB Output is correct
3 Correct 20 ms 42620 KB Output is correct
4 Correct 26 ms 42520 KB Output is correct
5 Correct 21 ms 42572 KB Output is correct
6 Correct 19 ms 42572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 42696 KB Output is correct
2 Correct 121 ms 42804 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 42696 KB Output is correct
2 Correct 121 ms 42804 KB Output is correct
3 Correct 156 ms 42920 KB Output is correct
4 Correct 153 ms 43140 KB Output is correct
5 Correct 174 ms 43208 KB Output is correct
6 Execution timed out 204 ms 43292 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42612 KB Output is correct
2 Correct 19 ms 42628 KB Output is correct
3 Correct 20 ms 42620 KB Output is correct
4 Correct 26 ms 42520 KB Output is correct
5 Correct 21 ms 42572 KB Output is correct
6 Correct 19 ms 42572 KB Output is correct
7 Correct 90 ms 42696 KB Output is correct
8 Correct 121 ms 42804 KB Output is correct
9 Correct 101 ms 42896 KB Output is correct
10 Correct 122 ms 42648 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42612 KB Output is correct
2 Correct 19 ms 42628 KB Output is correct
3 Correct 20 ms 42620 KB Output is correct
4 Correct 26 ms 42520 KB Output is correct
5 Correct 21 ms 42572 KB Output is correct
6 Correct 19 ms 42572 KB Output is correct
7 Correct 90 ms 42696 KB Output is correct
8 Correct 121 ms 42804 KB Output is correct
9 Correct 156 ms 42920 KB Output is correct
10 Correct 153 ms 43140 KB Output is correct
11 Correct 174 ms 43208 KB Output is correct
12 Execution timed out 204 ms 43292 KB Time limit exceeded
13 Halted 0 ms 0 KB -