oj.uz

답안 #331730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
331730 2020-11-29T19:27:39 Z valerikk Lucky Numbers (RMI19_lucky) C++17
46 / 100
 171 ms 7684 KB 
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
typedef long long ll;

const int M = 1e9 + 7;

vector<vector<int>> mul(const vector<vector<int>> &a, const vector<vector<int>> &b) {
    vector<vector<int>> res(4, vector<int>(4, 0));
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            for (int k = 0; k < 4; ++k) {
                res[i][j] += (ll)a[i][k] * b[k][j] % M;
                if (res[i][j] >= M) res[i][j] -= M;
            }
        }
    }
    return res;
}

vector<vector<int>> get(int d) {
    vector<vector<int>> res(4, vector<int>(4, 0));
    for (int i = 0; i < 4; ++i) {
        int good = (i & 1), bad = (i & 2);
        for (int x = 0; x < 10; ++x) {
            if (x > d && !good) break;
            if (x == 3 && bad) continue;
            int good1 = good, bad1 = 0;
            if (x < d) good1 = 1;
            if (x == 1) bad1 = 1;
            ++res[i][good1 + bad1 * 2];
        }
    }
    return res;
}

const int N = 1e5 + 7;

vector<vector<int>> t[N];
string s;

void build(int v, int tl, int tr) {
    if (tr - tl == 1) t[v] = get(s[tl] - '0'); else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm, tr);
        t[v] = mul(t[2 * v], t[2 * v + 1]);
    }
}

void update(int v, int tl, int tr, int pos, char x) {
    if (tr - tl == 1) {
        s[tl] = x;
        t[v] = get(x - '0');
    } else {
        int tm = (tl + tr) / 2;
        if (pos < tm) update(2 * v, tl, tm, pos, x); else update(2 * v + 1, tm, tr, pos, x);
        t[v] = mul(t[2 * v], t[2 * v + 1]);
    }
}

vector<vector<int>> query(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
    if (tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return mul(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm, tr, l, r));
}

int get_ans(const vector<vector<int>> &res) {
    int ans = 0;
    for (int i = 0; i < 4; ++i) {
        ans += res[0][i];
        if (ans >= M) ans -= M;
    }
    return ans;
}

int main() {
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q >> s;
    build(1, 0, n);
    cout << get_ans(t[1]) << '\n';
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            --l;
            cout << get_ans(query(1, 0, n, l, r)) << '\n';
        } else {
            int pos;
            string x;
            cin >> pos >> x;
            --pos;
            update(1, 0, n, pos, x[0]);
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 6636 KB Output is correct
2 Correct 171 ms 7684 KB Output is correct

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 6636 KB Output is correct
2 Correct 171 ms 7684 KB Output is correct
3 Runtime error 6 ms 5868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 134 ms 6636 KB Output is correct
8 Correct 171 ms 7684 KB Output is correct
9 Correct 101 ms 6636 KB Output is correct
10 Correct 141 ms 7680 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 134 ms 6636 KB Output is correct
8 Correct 171 ms 7684 KB Output is correct
9 Runtime error 6 ms 5868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -