Submission #1111145

#TimeUsernameProblemLanguageResultExecution timeMemory
1111145fryingducLucky Numbers (RMI19_lucky)C++17
100 / 100
34 ms27548 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include "bits/stdc++.h" using namespace std; #ifdef duc_debug #include "bits/debug.h" #else #define debug(...) #endif #define int long long const int maxn = 2e5+5; const int mod = 1e9+7; int n, q; string s; int p[maxn]; void prec(){ p[0] = 1, p[1] = 10; for(int i = 2; i < maxn; ++i){ p[i] = (p[i - 1] * 10 - p[i - 2] + mod * mod) % mod; } } struct Node{ int val, ft, lt, both; int sz, check; int ft_pos, lt_pos; friend Node operator + (const Node &a, const Node &b){ if(a.sz == 0) return b; if(b.sz == 0) return a; Node res; res.sz = a.sz + b.sz; res.ft_pos = a.ft_pos, res.lt_pos = b.lt_pos; if(a.lt_pos == 1 and b.ft_pos == 3) res.check = 0; else res.check = (a.check & b.check); bool gud = (a.check and a.ft_pos == 3); bool nice = (a.check and a.lt_pos == 1); res.val = (a.val - a.check) * p[b.sz] + (a.check ? b.val : 0); res.ft = (a.ft - gud) * p[b.sz] + (gud ? b.val : 0); res.lt = (a.val - a.check) * p[b.sz - 1] + (a.check ? b.lt : 0); res.both = (a.ft - gud) * p[b.sz - 1] + (gud ? b.lt : 0); res.val -= ((a.lt - nice) * p[b.sz - 1] + (nice ? b.ft : 0)); res.ft -= ((a.both - (gud and nice)) * p[b.sz - 1] + (gud and nice ? b.ft : 0)); if(b.sz >= 2) res.lt -= ((a.lt - nice) * p[b.sz - 2] + (nice ? b.both : 0)); if(b.sz >= 2) res.both -= ((a.both - (gud and nice)) * p[b.sz - 2] + (gud and nice ? b.both : 0)); res.val = (res.val + mod * mod) % mod; res.ft = (res.ft + mod * mod) % mod; res.lt = (res.lt + mod * mod) % mod; res.both = (res.both + mod * mod) % mod; // debug(res.sz, res.ft_pos, res.lt_pos, res.val, res.ft, res.lt); return res; } }; Node emp = {0, 0, 0, 0, 0, 0, 0, 0}; struct SegTree{ int n; vector<Node> tree; void init(int sz){ n = sz; tree.resize(n * 4 + 6, emp); } void build(int ind, int l, int r){ if(l == r){ int c = s[l] - '0' + 1; tree[ind] = Node({c, (c > 3), (c > 1), 0, 1, 1, c - 1, c - 1}); return; } int mid = (l + r) / 2; build(ind * 2, l, mid); build(ind * 2 + 1, mid + 1, r); tree[ind] = tree[ind * 2] + tree[ind * 2 + 1]; // debug(ind, l, r, tree[ind].val); } void update(int ind, int l, int r, int pos, int val){ if(l == r){ ++val; tree[ind] = Node({val, (val > 3), (val > 1), 0, 1, 1, val - 1, val - 1}); return; } int mid = (l + r) / 2; if(l <= pos and pos <= mid) update(ind * 2, l, mid, pos, val); else update(ind * 2 + 1, mid + 1, r, pos, val); tree[ind] = tree[ind * 2] + tree[ind * 2 + 1]; } Node get(int ind, int l, int r, int x, int y){ if(l > y || r < x) return emp; if(x <= l and r <= y) return tree[ind]; int mid = (l + r) / 2; return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y); } void update(int pos, int val){ update(1, 1, n, pos, val); } Node get(int x, int y){ return get(1, 1, n, x, y); } } st; void solve(){ prec(); // debug(p[0], p[1], p[2], p[3]); cin >> n >> q; cin >> s; s = ' ' + s; st.init(n); st.build(1, 1, n); cout << st.get(1, n).val << '\n'; // debug(st.get(1, 2).val_tight, st.get(1, 1).val_tight); for(int i = 1; i <= q; ++i){ int op, l, r; cin >> op >> l >> r; if(op == 1){ cout << st.get(l, r).val << '\n'; } else{ st.update(l, r); } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int test = 1; // cin >> test; for(int i = 1; i <= test; i++){ // cout << "Case " << "#" << i << ": "; solve(); } cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; 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...