Submission #711480

#TimeUsernameProblemLanguageResultExecution timeMemory
711480NursikLucky Numbers (RMI19_lucky)C++17
100 / 100
124 ms38436 KiB
#include <iostream> #include <fstream> #include <iomanip> #include <vector> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <ctime> #include <algorithm> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <cstdlib> #include <cstdio> #include <iterator> #include <functional> #include <unordered_set> #include <unordered_map> #include <stdio.h> #include <bitset> #include <cstdint> #include <cassert> #include <functional> #include <complex> #include <random> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second #define ld long double const ll maxn = 1e5 + 1, maxm = 1e4 + 1; const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, block = 5000, p2 = 31, bit = 30; const ld eps = 1e-9; int n, q; string s; struct node{ ll s[2][2]; ll e[2][2]; ll b[2][2]; node(){ for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ s[i][j] = 0; e[i][j] = 0; b[i][j] = 0; } } } } t[maxn * 4]; node merge(node lx, node rx){ node cur; for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ cur.s[i][j] = 0; cur.e[i][j] = 0; cur.b[i][j] = 0; } } for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ for (int jj = 0; jj < 2; ++jj){ for (int k = 0; k < 2; ++k){ if (!(j == 1 && jj == 1)){ cur.s[i][k] = (cur.s[i][k] + lx.s[i][j] * rx.s[jj][k] % mod) % mod; cur.s[i][k] = (cur.s[i][k] + lx.s[i][j] * rx.e[jj][k] % mod) % mod; cur.s[i][k] = (cur.s[i][k] + lx.s[i][j] * rx.b[jj][k] % mod) % mod; cur.s[i][k] = (cur.s[i][k] + lx.e[i][j] * rx.s[jj][k] % mod) % mod; cur.e[i][k] = (cur.e[i][k] + lx.e[i][j] * rx.e[jj][k] % mod) % mod; cur.b[i][k] = (cur.b[i][k] + lx.e[i][j] * rx.b[jj][k] % mod) % mod; cur.b[i][k] = (cur.b[i][k] + lx.b[i][j] * rx.e[jj][k] % mod) % mod; cur.b[i][k] = (cur.b[i][k] + lx.b[i][j] * rx.s[jj][k] % mod) % mod; cur.b[i][k] = (cur.b[i][k] + lx.b[i][j] * rx.b[jj][k] % mod ) % mod; } } } } } return cur; } void build(int v = 1, int tl = 1, int tr = n){ if (tl == tr){ for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ t[v].s[i][j] = 0; t[v].e[i][j] = 0; t[v].b[i][j] = 0; } } int val = s[tl] - '0'; for (int i = 0; i <= 9; ++i){ if (i < val){ if (i == 1){ t[v].s[0][1] += 1; } else if (i == 3){ t[v].s[1][0] += 1; } else{ t[v].s[0][0] += 1; } } else if (i == val){ if (i == 1){ t[v].e[0][1] += 1; } else if (i == 3){ t[v].e[1][0] += 1; } else{ t[v].e[0][0] += 1; } } else{ if (i == 1){ t[v].b[0][1] += 1; } else if (i == 3){ t[v].b[1][0] += 1; } else{ t[v].b[0][0] += 1; } } } return; } int tm = (tl + tr) / 2; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); t[v] = merge(t[v + v], t[v + v + 1]); /*cout << v << '\n'; cout << tl << " " << tr << '\n'; cout << t[v].s[0][0] << " " << t[v].s[0][1] << " " << t[v].s[1][0] << " " << t[v].s[1][1] << '\n'; cout << t[v].e[0][0] << " " << t[v].e[0][1] << " " << t[v].e[1][0] << " " << t[v].e[1][1] << '\n'; cout << t[v].b[0][0] << " " << t[v].b[0][1] << " " << t[v].b[1][0] << " " << t[v].b[1][1] << '\n';*/ } void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){ if (tl == tr){ for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ t[v].s[i][j] = 0; t[v].e[i][j] = 0; t[v].b[i][j] = 0; } } for (int i = 0; i <= 9; ++i){ if (i < val){ if (i == 1){ t[v].s[0][1] += 1; } else if (i == 3){ t[v].s[1][0] += 1; } else{ t[v].s[0][0] += 1; } } else if (i == val){ if (i == 1){ t[v].e[0][1] += 1; } else if (i == 3){ t[v].e[1][0] += 1; } else{ t[v].e[0][0] += 1; } } else{ if (i == 1){ t[v].b[0][1] += 1; } else if (i == 3){ t[v].b[1][0] += 1; } else{ t[v].b[0][0] += 1; } } } return; } int tm = (tl + tr) / 2; if (pos <= tm){ upd(pos, val, v + v, tl, tm); } else{ upd(pos, val, v + v + 1, tm + 1, tr); } t[v] = merge(t[v + v], t[v + v + 1]); } node get(int l, int r, int v = 1, int tl = 1, int tr = n){ if (l <= tl && tr <= r){ return t[v]; } int tm = (tl + tr) / 2; if (r <= tm){ return get(l, r, v + v, tl, tm); } if (l > tm){ return get(l, r, v + v + 1, tm + 1, tr); } return merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr)); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> q; cin >> s; s = '#' + s; build(); ll answ = 0; for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ answ = (answ + t[1].s[i][j] + t[1].e[i][j]) % mod; } } cout << answ << '\n'; // exit(0); for (int type, l, r, pos, dig, i = 1; i <= q; ++i){ cin >> type; if (type == 1){ cin >> l >> r; node ans = get(l, r); answ = 0; for (int j = 0; j < 2; ++j){ for (int k = 0; k < 2; ++k){ answ = (answ + ans.s[j][k] + ans.e[j][k]) % mod; } } cout << answ << '\n'; } else{ cin >> pos >> dig; upd(pos, dig); } } } /* ajj, ajj, ajj, ajj, aj, aj, aj, aj, aj, aj, ak, ak, ak, ak, ak, ai, ai, ai */
#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...