Submission #1197997

#TimeUsernameProblemLanguageResultExecution timeMemory
119799712345678Lucky Numbers (RMI19_lucky)C++20
28 / 100
1095 ms680 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5, mod=1e9+7; int n, q, t, l, r, s[nx], dp[nx][2][2], f; // dp[digit][not 3 / anything][tight?] char c; 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'; 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<2; j++) dp[i][j][0]=dp[i][j][1]=0; for (int j=0; j<2; j++) dp[r+1][j][0]=dp[r+1][j][1]=1; for (int i=r; i>=l; i--) { for (int tight=0; tight<2; tight++) { int lb=0, ub=tight?s[i]:9; for (int d=lb; d<=ub; d++) { if (d==1) dp[i][1][tight]=(dp[i][1][tight]+dp[i+1][0][tight&(d==ub)])%mod; else dp[i][1][tight]=(dp[i][1][tight]+dp[i+1][1][tight&(d==ub)])%mod; if (d!=3) { if (d==1) dp[i][0][tight]=(dp[i][0][tight]+dp[i+1][0][tight&(d==ub)])%mod; else dp[i][0][tight]=(dp[i][0][tight]+dp[i+1][1][tight&(d==ub)])%mod; } } } //cout<<"not tight "<<i<<" : "<<dp[i][0][0]<<' '<<dp[i][1][0]<<'\n'; //cout<<"debug "<<i<<" : "<<dp[i][0][1]<<' '<<dp[i][1][1]<<'\n'; } cout<<dp[l][1][1]<<'\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...