Submission #272382

#	Time	Username	Problem	Language	Result	Execution time	Memory
272382		Fasho	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	77 ms	11000 KiB

lucky

#include <bits/stdc++.h>
#define N 100005
#define ll long long int
#define fo(i,x,y)   for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define mod 1000000007
using namespace std;

ll n,m,ar[N],sum,t,dp[N][2];

char s[N];

ll add(ll x,ll y)
{
    x%=mod;
    y%=mod;
    x+=y;
    x%=mod;
    x+=mod;
    x%=mod;
    return x;

}

ll f(int len,int tut)
{
    if(len==0)
        return 1;
    if(dp[len][tut]!=-1)
        return dp[len][tut];
    ll top=0;
    fo(i,0,9)
    {
        if(tut && i==3)
            continue;
        ll x=0;
        if(i==1)
            x=1;
        top=add(top,f(len-1,x));
    }
    return dp[len][tut]=top;
}
// int get(int l,int r){
//  int len=r-l;
//  int ans=0;
    
//  int flag=0;
//  rep(x,l,r+1){
//      rep(y,0,ar[x]){
//          if (flag && y==3) continue;
//          ans=(ans+f(len,y==1))%mod;
//      }
        
//      if (ar[x]==1) flag=1;
//      else if (flag && ar[x]==3) return ans;
//      else flag=0;
//      len--;
//  }
    
//  return (ans+1)%mod;
// }


void get(int l,int r){
    int len=r-l;
    int ans=0;
    
    int flag=0;
    fo(x,l,r){
        fo(y,0,ar[x]-1){
            if (flag && y==3) continue;
            ans=(ans+f(len,y==1))%mod;
        }
        
        if (ar[x]==1) flag=1;
        else if (flag && ar[x]==3)
        { sum=ans;
            return;
        }
        else flag=0;
        len--;
    }
    
    sum=(ans+1)%mod;
}

int main()
{
    fast;
    cin>>n>>m;
    cin>>s+1;
    fo(i,1,n)
        ar[i]=s[i]-'0';
    memset(dp,-1,sizeof(dp));
    // cout<<f(1,n)<<endl;
    // cout<<get(1,n);
    get(1,n);
    cout<<sum<<endl;
    while(m--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        if(a==2)
            ar[b]=c;
        else
        {
            get(b,c);
            cout<<sum<<endl;
        }
    }
} 

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:99:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     cin>>s+1;
      |          ~^~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27