oj.uz

Submission #532166

# Submission time Handle Problem Language Result Execution time Memory
532166 2022-03-02T08:13:20 Z i_am_noob Lucky Numbers (RMI19_lucky) C++17
100 / 100
 31 ms 22764 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

const int mod=1000000007;
const int maxn=100005,maxm=5,maxk=7777714;

//i_am_noob
int dp[maxn][2],dp2[maxn][2];//0: ends with anything but 3, 1: ends with 3

struct obj{
    int len;//length of the number
    int val0,val1;//# of ways end with {not 1, 1}
    bool good;//does not contain "13"
    int begin,end;//first digit, last digit
    obj(){len=0;}
    void set(int x){
        len=1;
        if(x>1) val1=1;
        else val1=0;
        val0=x-val1;
        good=1;
        begin=end=x;
    }
};

obj Merge(obj x, obj y){
    if(x.len==0) return y;
    if(y.len==0) return x;
    obj res;
    res.len=x.len+y.len;
    res.good=1;
    if(x.end==1&&y.begin==3) res.good=0;
    if((!x.good)||(!y.good)) res.good=0;
    res.begin=x.begin;
    res.end=y.end;
    res.val0=res.val1=0;
    res.val0+=(dp[y.len][0]*8+dp[y.len][1])%mod*x.val0+(dp2[y.len][0]*8+dp2[y.len][1])%mod*x.val1;
    res.val0%=mod;
    res.val1+=dp[y.len][0]*x.val0+dp2[y.len][0]*x.val1;
    res.val1%=mod;
    if(!x.good){}
    else if(x.end!=1){
        res.val0+=y.val0; res.val0%=mod;
        res.val1+=y.val1; res.val1%=mod;
    }
    else if(y.begin!=3){
        res.val0+=y.val0; res.val0%=mod;
        res.val1+=y.val1; res.val1%=mod;
        if(y.begin>3){
            if(y.len==1){
                res.val0--;
                if(res.val0<0) res.val0+=mod;
            }
            else{
                res.val0-=(dp[y.len-1][0]*8+dp[y.len-1][1])%mod; res.val0+=mod; res.val0%=mod;
                res.val1-=dp[y.len-1][0]; res.val1+=mod; res.val1%=mod;
            }
        }
    }
    else{
        if(y.len==1){
            res.val0+=2; res.val0%=mod;
            res.val1++; res.val1%=mod;
        }
        else{
            res.val0+=(dp[y.len-1][0]*8+dp[y.len-1][1])*2+(dp2[y.len-1][0]*8+dp2[y.len-1][1]);
            res.val0%=mod;
            res.val1+=(dp[y.len-1][0])*2+dp2[y.len-1][0];
            res.val1%=mod;
        }
    }
    return res;
}

obj node[maxn*4];
int n,q;
string str;

void pull(int k){node[k]=Merge(node[k<<1],node[k<<1|1]);}

void build(int k, int l, int r){
    if(l==r){
        node[k].set(str[l]-'0');
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    pull(k);
}

void modify(int k, int l, int r, int p, int x){
    if(l==r){
        node[k].set(x);
        return;
    }
    int mid=l+r>>1;
    if(p<=mid) modify(k<<1,l,mid,p,x);
    else modify(k<<1|1,mid+1,r,p,x);
    pull(k);
}

obj query(int k, int l, int r, int ql, int qr){
    if(l>qr||r<ql) return obj();
    if(ql<=l&&qr>=r){
        return node[k];
    }
    int mid=l+r>>1;
    return Merge(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr));
}

int query(int l, int r){
    obj res=query(1,0,n-1,l,r);
    int tot=res.val0+res.val1;
    if(res.good) tot++;
    tot+=mod;
    tot%=mod;
    return tot;
}

void print(int k, int l, int r){
    bug(l,r,node[k].val0,node[k].val1);
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    print(k<<1,l,mid),print(k<<1|1,mid+1,r);
}

void orzck(){
    dp[1][0]=dp[1][1]=1;
    rep2(i,2,maxn) dp[i][0]=(dp[i-1][0]*9+dp[i-1][1])%mod,dp[i][1]=(dp[i-1][0]*8+dp[i-1][1])%mod;
    dp2[1][0]=1,dp2[1][1]=0;
    rep2(i,2,maxn) dp2[i][0]=(dp2[i-1][0]*9+dp2[i-1][1])%mod,dp2[i][1]=(dp2[i-1][0]*8+dp2[i-1][1])%mod;
    cin >> n >> q >> str;
    build(1,0,n-1);
    cout << query(0,n-1) << "\n";
    while(q--){
        int op;
        cin >> op;
        if(op==1){
            int l,r;
            cin >> l >> r;
            l--,r--;
            cout << query(l,r) << "\n";
        }
        else{
            int p,x;
            cin >> p >> x;
            p--;
            modify(1,0,n-1,p,x);
        }
    }
    //print(1,0,n-1);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    orzck();
    return 0;
}

Compilation message

lucky.cpp: In function 'void build(long long int, long long int, long long int)':
lucky.cpp:116:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int mid=l+r>>1;
      |             ~^~
lucky.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int)':
lucky.cpp:126:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |     int mid=l+r>>1;
      |             ~^~
lucky.cpp: In function 'obj query(long long int, long long int, long long int, long long int, long long int)':
lucky.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |     int mid=l+r>>1;
      |             ~^~
lucky.cpp: In function 'void print(long long int, long long int, long long int)':
lucky.cpp:31:18: warning: statement has no effect [-Wunused-value]
   31 | #define bug(...) 777771449
      |                  ^~~~~~~~~
lucky.cpp:151:5: note: in expansion of macro 'bug'
  151 |     bug(l,r,node[k].val0,node[k].val1);
      |     ^~~
lucky.cpp:155:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Correct 11 ms 22220 KB Output is correct
3 Correct 10 ms 22232 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Correct 11 ms 22220 KB Output is correct
3 Correct 10 ms 22232 KB Output is correct
4 Correct 10 ms 22120 KB Output is correct
5 Correct 11 ms 22112 KB Output is correct
6 Correct 11 ms 22224 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22348 KB Output is correct
2 Correct 20 ms 22412 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22348 KB Output is correct
2 Correct 20 ms 22412 KB Output is correct
3 Correct 31 ms 22660 KB Output is correct
4 Correct 25 ms 22624 KB Output is correct
5 Correct 24 ms 22636 KB Output is correct
6 Correct 25 ms 22756 KB Output is correct
7 Correct 28 ms 22764 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Correct 11 ms 22220 KB Output is correct
3 Correct 10 ms 22232 KB Output is correct
4 Correct 10 ms 22120 KB Output is correct
5 Correct 11 ms 22112 KB Output is correct
6 Correct 11 ms 22224 KB Output is correct
7 Correct 18 ms 22348 KB Output is correct
8 Correct 20 ms 22412 KB Output is correct
9 Correct 17 ms 22332 KB Output is correct
10 Correct 24 ms 22312 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Correct 11 ms 22220 KB Output is correct
3 Correct 10 ms 22232 KB Output is correct
4 Correct 10 ms 22120 KB Output is correct
5 Correct 11 ms 22112 KB Output is correct
6 Correct 11 ms 22224 KB Output is correct
7 Correct 18 ms 22348 KB Output is correct
8 Correct 20 ms 22412 KB Output is correct
9 Correct 31 ms 22660 KB Output is correct
10 Correct 25 ms 22624 KB Output is correct
11 Correct 24 ms 22636 KB Output is correct
12 Correct 25 ms 22756 KB Output is correct
13 Correct 28 ms 22764 KB Output is correct
14 Correct 17 ms 22332 KB Output is correct
15 Correct 24 ms 22312 KB Output is correct
16 Correct 21 ms 22492 KB Output is correct
17 Correct 22 ms 22604 KB Output is correct
18 Correct 24 ms 22672 KB Output is correct
19 Correct 27 ms 22648 KB Output is correct
20 Correct 27 ms 22596 KB Output is correct