Submission #636832

#TimeUsernameProblemLanguageResultExecution timeMemory
636832ogibogi2004Lucky Numbers (RMI19_lucky)C++14
28 / 100
174 ms1272 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=1e9+7; const ll MAXN=1e5+6; ll dp[MAXN]; int n,q; ll a[MAXN]; ll solve(int l,int r) { ll ans=0; for(int i=l;i<=r;i++) { if(i>l+1&&a[i-2]==1&&a[i-1]==3)continue; ans+=a[i]*dp[r-i]; if(a[i]>1&&i<r)ans-=dp[r-i-1]; if(i!=l&&a[i-1]==1&&a[i]>3)ans-=dp[r-i]; ans+=mod; ans%=mod; //cout<<i<<" "<<a[i]<<" "<<ans<<endl; } bool flag=1; for(int i=l;i+1<=r;i++) { if(a[i]==1&&a[i+1]==3)flag=0; } if(flag)ans++; return ans; } void precompute() { dp[0]=1; dp[1]=10; for(int i=2;i<MAXN;i++) { dp[i]=dp[i-1]*10-dp[i-2]; dp[i]+=mod; dp[i]%=mod; } } int main() { cin>>n>>q; precompute(); for(int i=1;i<=n;i++) { char c; cin>>c; a[i]=c-'0'; } cout<<solve(1,n)<<endl; for(int i=0;i<q;i++) { int t,x,y; cin>>t>>x>>y; if(t==1)cout<<solve(x,y)<<endl; else a[x]=y; } 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...