oj.uz

Submission #494259

# Submission time Handle Problem Language Result Execution time Memory
494259 2021-12-14T22:02:30 Z Bliznetc Lucky Numbers (RMI19_lucky) C++17
100 / 100
 187 ms 43232 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 42552 KB Output is correct
2 Correct 17 ms 42572 KB Output is correct
3 Correct 16 ms 42572 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 42552 KB Output is correct
2 Correct 17 ms 42572 KB Output is correct
3 Correct 16 ms 42572 KB Output is correct
4 Correct 18 ms 42572 KB Output is correct
5 Correct 18 ms 42612 KB Output is correct
6 Correct 22 ms 42596 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 42696 KB Output is correct
2 Correct 96 ms 42668 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 42696 KB Output is correct
2 Correct 96 ms 42668 KB Output is correct
3 Correct 134 ms 42964 KB Output is correct
4 Correct 148 ms 42920 KB Output is correct
5 Correct 169 ms 43048 KB Output is correct
6 Correct 169 ms 43136 KB Output is correct
7 Correct 172 ms 43232 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 42552 KB Output is correct
2 Correct 17 ms 42572 KB Output is correct
3 Correct 16 ms 42572 KB Output is correct
4 Correct 18 ms 42572 KB Output is correct
5 Correct 18 ms 42612 KB Output is correct
6 Correct 22 ms 42596 KB Output is correct
7 Correct 76 ms 42696 KB Output is correct
8 Correct 96 ms 42668 KB Output is correct
9 Correct 85 ms 42660 KB Output is correct
10 Correct 115 ms 42812 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 42552 KB Output is correct
2 Correct 17 ms 42572 KB Output is correct
3 Correct 16 ms 42572 KB Output is correct
4 Correct 18 ms 42572 KB Output is correct
5 Correct 18 ms 42612 KB Output is correct
6 Correct 22 ms 42596 KB Output is correct
7 Correct 76 ms 42696 KB Output is correct
8 Correct 96 ms 42668 KB Output is correct
9 Correct 134 ms 42964 KB Output is correct
10 Correct 148 ms 42920 KB Output is correct
11 Correct 169 ms 43048 KB Output is correct
12 Correct 169 ms 43136 KB Output is correct
13 Correct 172 ms 43232 KB Output is correct
14 Correct 85 ms 42660 KB Output is correct
15 Correct 115 ms 42812 KB Output is correct
16 Correct 148 ms 43092 KB Output is correct
17 Correct 147 ms 43116 KB Output is correct
18 Correct 171 ms 43148 KB Output is correct
19 Correct 187 ms 43212 KB Output is correct
20 Correct 178 ms 43152 KB Output is correct