oj.uz

Submission #272382

# Submission time Handle Problem Language Result Execution time Memory
272382 2020-08-18T11:37:52 Z Fasho Lucky Numbers (RMI19_lucky) C++14
100 / 100
 77 ms 11000 KB 
#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 2 ms 1920 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2808 KB Output is correct
2 Correct 56 ms 2944 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2808 KB Output is correct
2 Correct 56 ms 2944 KB Output is correct
3 Correct 59 ms 9120 KB Output is correct
4 Correct 73 ms 9240 KB Output is correct
5 Correct 73 ms 10000 KB Output is correct
6 Correct 77 ms 10956 KB Output is correct
7 Correct 76 ms 11000 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 2 ms 1920 KB Output is correct
7 Correct 39 ms 2808 KB Output is correct
8 Correct 56 ms 2944 KB Output is correct
9 Correct 29 ms 2688 KB Output is correct
10 Correct 32 ms 3192 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 2 ms 1920 KB Output is correct
7 Correct 39 ms 2808 KB Output is correct
8 Correct 56 ms 2944 KB Output is correct
9 Correct 59 ms 9120 KB Output is correct
10 Correct 73 ms 9240 KB Output is correct
11 Correct 73 ms 10000 KB Output is correct
12 Correct 77 ms 10956 KB Output is correct
13 Correct 76 ms 11000 KB Output is correct
14 Correct 29 ms 2688 KB Output is correct
15 Correct 32 ms 3192 KB Output is correct
16 Correct 43 ms 9088 KB Output is correct
17 Correct 47 ms 9088 KB Output is correct
18 Correct 54 ms 9984 KB Output is correct
19 Correct 64 ms 10872 KB Output is correct
20 Correct 68 ms 10880 KB Output is correct