Submission #645746

#TimeUsernameProblemLanguageResultExecution timeMemory
645746Alex_tz307Lucky Numbers (RMI19_lucky)C++17
100 / 100
80 ms13120 KiB
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; string s; void addSelf(int &x, int y) { x += y; if (x >= mod) { x -= mod; } } int mult(int x, int y) { return (int64_t)x * y % mod; } struct node { int small[2][2], eq[2][2], big[2][2]; /// small - strict mai mic /// eq - egal /// big - strict mai mare /// 00 - nu incepe cu 3, nu se termina cu 1 /// 01 - nu incepe cu 3, se termina cu 1 /// 10 - incepe cu 3, nu se termina cu 1 /// 11 - incepe cu 3, se termina cu 1 void setLeaf(int c) { small[0][0] = c - (c > 1) - (c > 3); small[1][0] = (c > 3); small[0][1] = (c > 1); small[1][1] = 0; eq[0][0] = ((c != 1) && (c != 3)); eq[1][0] = (c == 3); eq[0][1] = (c == 1); eq[1][1] = 0; big[0][0] = 9 - c - (c < 1) - (c < 3); big[1][0] = (c < 3); big[0][1] = (c < 1); big[1][1] = 0; } node operator + (const node &rhs) const { node res; for (int left = 0; left <= 1; ++left) { for (int right = 0; right <= 1; ++right) { res.small[left][right] = 0; res.eq[left][right] = 0; res.big[left][right] = 0; for (int left1 = 0; left1 <= 1; ++left1) { for (int right3 = 0; right3 <= 1 - left1; ++right3) { addSelf(res.small[left][right], mult(small[left][left1], rhs.small[right3][right])); addSelf(res.small[left][right], mult(small[left][left1], rhs.eq[right3][right])); addSelf(res.small[left][right], mult(small[left][left1], rhs.big[right3][right])); addSelf(res.small[left][right], mult(eq[left][left1], rhs.small[right3][right])); addSelf(res.eq[left][right], mult(eq[left][left1], rhs.eq[right3][right])); addSelf(res.big[left][right], mult(eq[left][left1], rhs.big[right3][right])); addSelf(res.big[left][right], mult(big[left][left1], rhs.small[right3][right])); addSelf(res.big[left][right], mult(big[left][left1], rhs.eq[right3][right])); addSelf(res.big[left][right], mult(big[left][left1], rhs.big[right3][right])); } } } } return res; } }; struct ST { int n; vector<node> t; ST(int N) : n(N) { int dim = 1; while (dim < n) { dim *= 2; } t.resize(dim * 2); } void build(int x, int lx, int rx) { if (lx == rx) { t[x].setLeaf(s[lx] - '0'); return; } int mid = (lx + rx) / 2; build(x * 2, lx, mid); build(x * 2 + 1, mid + 1, rx); t[x] = t[x * 2] + t[x * 2 + 1]; } void update(int x, int lx, int rx, int pos) { if (lx == rx) { t[x].setLeaf(s[pos] - '0'); return; } int mid = (lx + rx) / 2; if (pos <= mid) { update(x * 2, lx, mid, pos); } else { update(x * 2 + 1, mid + 1, rx, pos); } t[x] = t[x * 2] + t[x * 2 + 1]; } void update(int pos) { update(1, 1, n, pos); } node query(int x, int lx, int rx, int st, int dr) { if (st <= lx && rx <= dr) { return t[x]; } int mid = (lx + rx) / 2; if (st <= mid && mid < dr) { return query(x * 2, lx, mid, st, dr) + query(x * 2 + 1, mid + 1, rx, st, dr); } else if (st <= mid) { return query(x * 2, lx, mid, st, dr); } else { return query(x * 2 + 1, mid + 1, rx, st, dr); } } node query(int st, int dr) { return query(1, 1, n, st, dr); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q >> s; s = '$' + s; ST t(n); t.build(1, 1, n); auto solve = [&](int x, int y) -> int { node res = t.query(x, y); int ans = 0; for (int i = 0; i <= 1; ++i) { for (int j = 0; j <= 1; ++j) { addSelf(ans, res.small[i][j]); addSelf(ans, res.eq[i][j]); } } return ans; }; cout << solve(1, n) << '\n'; for (int i = 0; i < q; ++i) { int op, x, y; cin >> op >> x >> y; if (op == 1) { cout << solve(x, y) << '\n'; } else if ((s[x] - '0') != y) { s[x] = '0' + y; t.update(x); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...