oj.uz

Submission #532161

# Submission time Handle Problem Language Result Execution time Memory
532161 2022-03-02T07:58:15 Z i_am_noob Lucky Numbers (RMI19_lucky) C++17
28 / 100
 18 ms 22348 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 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);
        }
    }
}

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;
      |             ~^~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22220 KB Output is correct
2 Correct 11 ms 22160 KB Output is correct
3 Correct 11 ms 22144 KB Output is correct
4 Correct 11 ms 22228 KB Output is correct
5 Correct 12 ms 22172 KB Output is correct
6 Correct 12 ms 22232 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 22348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 22348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22220 KB Output is correct
2 Correct 11 ms 22160 KB Output is correct
3 Correct 11 ms 22144 KB Output is correct
4 Correct 11 ms 22228 KB Output is correct
5 Correct 12 ms 22172 KB Output is correct
6 Correct 12 ms 22232 KB Output is correct
7 Incorrect 18 ms 22348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22220 KB Output is correct
2 Correct 11 ms 22160 KB Output is correct
3 Correct 11 ms 22144 KB Output is correct
4 Correct 11 ms 22228 KB Output is correct
5 Correct 12 ms 22172 KB Output is correct
6 Correct 12 ms 22232 KB Output is correct
7 Incorrect 18 ms 22348 KB Output isn't correct
8 Halted 0 ms 0 KB -