Submission #494248

#TimeUsernameProblemLanguageResultExecution timeMemory
494248BliznetcLucky Numbers (RMI19_lucky)C++17
0 / 100
115 ms42652 KiB
#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 1ll * (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 () { 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][j]); } } } 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); } } }
#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...