Submission #1198006

#TimeUsernameProblemLanguageResultExecution timeMemory
119800612345678Lucky Numbers (RMI19_lucky)C++20
28 / 100
560 ms840 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5, mod=1e9+7; #define ll long long ll n, q, t, l, r, s[nx], dp[nx][4], f, pre[10][4][4]; // dp[digit][not 3 / anything][tight?] char c; void precompute() { for (int cur=0; cur<=9; cur++) { for (int i=0; i<4; i++) { int any=i%2, tight=i/2; int lb=0, ub=tight?cur:9; for (int d=lb; d<=ub; d++) { if (any) { if (d==1) pre[cur][i][2*(tight&(d==ub))]++; else pre[cur][i][2*(tight&(d==ub))+1]++; } else { if (d!=3) { if (d==1) pre[cur][i][2*(tight&(d==ub))]++; else pre[cur][i][2*(tight&(d==ub))+1]++; } } } } } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>q; q++; for (int i=1; i<=n; i++) cin>>c, s[i]=c-'0'; precompute(); while (q--) { if (!f) f=1, t=1, l=1, r=n; else cin>>t>>l>>r; if (t==1) { for (int i=l; i<=r; i++) for (int j=0; j<4; j++) dp[i][j]=0; for (int j=0; j<4; j++) dp[r+1][j]=1; for (int i=r; i>=l; i--) { for (int j=0; j<4; j++) { for (int k=0; k<4; k++) dp[i][j]=(dp[i][j]+pre[s[i]][j][k]*dp[i+1][k])%mod; } } cout<<dp[l][3]<<'\n'; } else s[l]=r; } }
#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...