Submission #272715

#TimeUsernameProblemLanguageResultExecution timeMemory
272715Atill83Lucky Numbers (RMI19_lucky)C++14
64 / 100
51 ms28024 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 2e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n, q; ll pw[MAXN][3], dp[3][MAXN][3]; string s; struct node{ ll ans = 0, bit1 = 0, bas3 = 0; bool ok = 0; } t[2*MAXN]; void g(ll &a){ while(a < 0) a += mod; a %= mod; } void build(int v, int l, int r){ if(l == r){ t[v].ans = s[l] - '0'; if(t[v].ans >= 4){ t[v].bit1 = 1; t[v].bas3 = 1; }else if(t[v].ans > 1){ t[v].bit1 = 1; } t[v].ok = 1; }else{ int m = (l + r) / 2; build(2*v, l, m); build(2*v + 1, m + 1, r); int l2 = r - m; t[v].ans = 0; t[v].ans = (t[v].ans + t[2*v].ans*pw[l2][0]%mod)%mod; t[v].ans = (t[v].ans - (t[2*v].bit1*pw[l2][2]%mod) + mod)%mod; g(t[v].ans); t[v].ans = (t[v].ans + t[2*v].ok*t[2*v + 1].ans%mod)%mod; t[v].ans = (t[v].ans - (t[2*v].ok*(s[m] == '1')*t[2*v + 1].bas3%mod) + mod)%mod; g(t[v].ans); if(s[l] == '3'){ t[v].bas3 = (t[v].ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod; g(t[v].bas3); t[v].bas3 %= mod; }else if(s[l] >= '4'){ t[v].bas3 = pw[r - l][0]; }else{ t[v].bas3 = 0; } t[v].bit1 = 0; t[v].bit1 = (t[v].bit1 + t[2*v].ans*dp[0][l2][1]%mod)%mod; t[v].bit1 = (t[v].bit1 - t[2*v].bit1*dp[2][l2][1]%mod + mod)%mod; g(t[v].bit1); t[v].bit1 += t[2*v].ok*t[2*v + 1].bit1%mod; t[v].bit1 %= mod; if(s[m] == '1'){ if(s[m + 1] > '3'){ t[v].bit1 = (t[v].bit1 - t[2*v].ok*dp[0][r - m - 1][1]%mod + mod)%mod; g(t[v].bit1); }else if(s[m + 1] == '3'){ t[v].bit1 = (t[v].bit1 - t[2*v].ok*(t[2*v + 1].bit1 - 2*dp[0][r - m - 1][1]%mod - dp[1][r - m][1] + 2*mod)%mod + mod)%mod; g(t[v].bit1); } } if(s[m] == '1' && s[m + 1] == '3'){ t[v].ok = 0; }else{ t[v].ok = (t[2*v].ok && t[2*v + 1].ok); } } } void upd(int v, int l, int r, int pos, char val){ if(l == r){ s[l] = val; t[v].ans = s[l] - '0'; if(t[v].ans >= 4){ t[v].bit1 = 1; t[v].bas3 = 1; }else if(t[v].ans > 1){ t[v].bit1 = 1; } t[v].ok = 1; }else{ int m = (l + r) / 2; if(pos <= m) upd(2*v, l, m, pos, val); else upd(2*v + 1, m + 1, r, pos, val); int l2 = r - m; t[v].ans = 0; t[v].ans = (t[v].ans + t[2*v].ans*pw[l2][0]%mod)%mod; t[v].ans = (t[v].ans - (t[2*v].bit1*pw[l2][2]%mod) + mod)%mod; g(t[v].ans); t[v].ans = (t[v].ans + t[2*v].ok*t[2*v + 1].ans%mod)%mod; t[v].ans = (t[v].ans - (t[2*v].ok*(s[m] == '1')*t[2*v + 1].bas3%mod) + mod)%mod; g(t[v].ans); if(s[l] == '3'){ t[v].bas3 = (t[v].ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod; g(t[v].bas3); t[v].bas3 %= mod; }else if(s[l] >= '4'){ t[v].bas3 = pw[r - l][0]; }else{ t[v].bas3 = 0; } t[v].bit1 = 0; t[v].bit1 = (t[v].bit1 + t[2*v].ans*dp[0][l2][1]%mod)%mod; t[v].bit1 = (t[v].bit1 - t[2*v].bit1*dp[2][l2][1]%mod + mod)%mod; g(t[v].bit1); t[v].bit1 += t[2*v].ok*t[2*v + 1].bit1%mod; t[v].bit1 %= mod; if(s[m] == '1'){ if(s[m + 1] > '3'){ t[v].bit1 = (t[v].bit1 - t[2*v].ok*dp[0][r - m - 1][1]%mod + mod)%mod; g(t[v].bit1); }else if(s[m + 1] == '3'){ t[v].bit1 = (t[v].bit1 - t[2*v].ok*(t[2*v + 1].bit1 - 2*dp[0][r - m - 1][1]%mod - dp[1][r - m][1] + 2*mod)%mod + mod)%mod; g(t[v].bit1); } } if(s[m] == '1' && s[m + 1] == '3'){ t[v].ok = 0; }else{ t[v].ok = (t[2*v].ok && t[2*v + 1].ok); } } } node que(int v, int tl, int tr, int l, int r){ if(l > r){ node a = {-1, -1, -1, 0}; return a; }else if(l == tl && r == tr){ return t[v]; }else{ int tm = (tl + tr) / 2; node left = que(2*v, tl, tm, l, min(tm, r)), right = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r); if(r <= tm){ return left; }else if(l >= tm + 1){ return right; }else{ node res; int l2 = r - tm; res.ans = 0; res.ans = (res.ans + left.ans*pw[l2][0]%mod)%mod; res.ans = (res.ans - (left.bit1*pw[l2][2]%mod) + mod)%mod; g(res.ans); res.ans = (res.ans + left.ok*right.ans%mod)%mod; res.ans = (res.ans - (left.ok*(s[tm] == '1')*right.bas3%mod) + mod)%mod; g(res.ans); if(s[l] == '3'){ res.bas3 = (res.ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod; g(res.bas3); res.bas3 %= mod; }else if(s[l] >= '4'){ res.bas3 = pw[r - l][0]; }else{ res.bas3 = 0; } res.bit1 = 0; res.bit1 = (res.bit1 + left.ans*dp[0][l2][1]%mod)%mod; res.bit1 = (res.bit1 - left.bit1*dp[2][l2][1]%mod + mod)%mod; g(res.bit1); res.bit1 += left.ok*right.bit1%mod; res.bit1 %= mod; if(s[tm] == '1'){ if(s[tm + 1] > '3'){ res.bit1 = (res.bit1 - left.ok*dp[0][r - tm - 1][1]%mod + mod)%mod; }else if(s[tm + 1] == '3'){ res.bit1 = (res.bit1 - left.ok*(right.bit1 - 2*dp[0][r - tm - 1][1]%mod - dp[1][r - tm][1] + 2*mod)%mod + mod)%mod; } g(res.bit1); } if(s[tm] == '1' && s[tm + 1] == '3'){ res.ok = 0; }else{ res.ok = (left.ok && right.ok); } return res; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif cin>>n>>q; pw[0][0] = 0; dp[0][1][0] = 8; dp[0][1][1] = 1; dp[0][1][2] = 1; pw[1][0] = 10; for(int i = 2; i < MAXN ; i++){ dp[0][i][0] = (dp[0][i - 1][0] + dp[0][i - 1][1] + dp[0][i - 1][2])%mod*8 % mod; dp[0][i][1] = (dp[0][i - 1][0] + dp[0][i - 1][1] + dp[0][i - 1][2])%mod; dp[0][i][2] = (dp[0][i - 1][0] + dp[0][i - 1][2])%mod; pw[i][0] = (dp[0][i][0] + dp[0][i][1] + dp[0][i][2])%mod; } pw[0][1] = 0; dp[1][1][1] = 1; pw[1][1] = 1; for(int i = 2; i < MAXN ; i++){ dp[1][i][0] = (dp[1][i - 1][0] + dp[1][i - 1][1] + dp[1][i - 1][2])%mod*8 % mod; dp[1][i][1] = (dp[1][i - 1][0] + dp[1][i - 1][1] + dp[1][i - 1][2])%mod; dp[1][i][2] = (dp[1][i - 1][0] + dp[1][i - 1][2])%mod; pw[i][1] = (dp[1][i][0] + dp[1][i][1] + dp[1][i][2])%mod; } pw[0][2] = 0; dp[2][1][2] = 1; pw[1][2] = 1; for(int i = 2; i < MAXN ; i++){ dp[2][i][0] = (dp[2][i - 1][0] + dp[2][i - 1][1] + dp[2][i - 1][2])%mod*8% mod; dp[2][i][1] = (dp[2][i - 1][0] + dp[2][i - 1][1] + dp[2][i - 1][2])%mod; dp[2][i][2] = (dp[2][i - 1][0] + dp[2][i - 1][2])%mod; pw[i][2] = (dp[2][i][0] + dp[2][i][1] + dp[2][i][2])%mod; } cin>>s; build(1, 0, n - 1); node cr = que(1, 0, n - 1, 0, n - 1); cout<<(cr.ans + cr.ok)%mod<<endl; while(q--){ int type; cin>>type; if(type == 1){ int l, r; cin>>l>>r; node cr = que(1, 0, n - 1, l - 1, r - 1); cout<<(cr.ans + cr.ok)%mod<<endl; }else{ int idx; char val; cin>>idx>>val; idx--; upd(1, 0, n - 1, idx, val); } } #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#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...