Submission #272732

#	Time	Username	Problem	Language	Result	Execution time	Memory
272732		Atill83	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	51 ms	27900 KiB

lucky

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, q;
ll pw[MAXN][3], dp[3][MAXN][3];

string s;

struct node{
    ll ans = 0, bit1 = 0, bas3 = 0;
    bool ok = 0;
} t[2*MAXN];
void g(ll &a){
    while(a < 0) a += mod;
    a %= mod;
}


void build(int v, int l, int r){
    if(l == r){
        t[v].ans = s[l] - '0';
        if(t[v].ans >= 4){
            t[v].bit1 = 1;
            t[v].bas3 = 1;
        }else if(t[v].ans > 1){
            t[v].bit1 = 1;
        }
        t[v].ok = 1;
    }else{
        int m = (l + r) / 2;
        build(2*v, l, m);
        build(2*v + 1, m + 1, r);

        int l2 = r - m;
        t[v].ans = 0;
        t[v].ans = (t[v].ans + t[2*v].ans*pw[l2][0]%mod)%mod;
        t[v].ans = (t[v].ans - (t[2*v].bit1*pw[l2][2]%mod) + mod)%mod;
        g(t[v].ans);
        t[v].ans = (t[v].ans + t[2*v].ok*t[2*v + 1].ans%mod)%mod;
        t[v].ans = (t[v].ans - (t[2*v].ok*(s[m] == '1')*t[2*v + 1].bas3%mod) + mod)%mod;
        g(t[v].ans);

        if(s[l] == '3'){
            t[v].bas3 = (t[v].ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod;
            g(t[v].bas3);
            t[v].bas3 %= mod;
        }else if(s[l] >= '4'){
            t[v].bas3 = pw[r - l][0];
        }else{
            t[v].bas3 = 0;
        }

        t[v].bit1 = 0;
        t[v].bit1 = (t[v].bit1 + t[2*v].ans*dp[0][l2][1]%mod)%mod;
        t[v].bit1 = (t[v].bit1 - t[2*v].bit1*dp[2][l2][1]%mod + mod)%mod;
        g(t[v].bit1);
        
        t[v].bit1 += t[2*v].ok*t[2*v + 1].bit1%mod;
        t[v].bit1 %= mod;

        if(s[m] == '1'){
            if(s[m + 1] > '3'){
                t[v].bit1 = (t[v].bit1 - t[2*v].ok*dp[2][r - m][1]%mod + mod)%mod;
                g(t[v].bit1);
            }else if(s[m + 1] == '3'){
                t[v].bit1 = (t[v].bit1 - t[2*v].ok*(t[2*v + 1].bit1 - 2*dp[0][r - m - 1][1]%mod - dp[1][r - m][1] + 2*mod)%mod + mod)%mod;
                g(t[v].bit1);
            }
        }


        if(s[m] == '1' && s[m + 1] == '3'){
            t[v].ok = 0;
        }else{
            t[v].ok = (t[2*v].ok && t[2*v + 1].ok);
        }
    }

}


void upd(int v, int l, int r, int pos){
    if(l == r){
        t[v].ans = s[l] - '0';
        if(t[v].ans >= 4){
            t[v].bit1 = 1;
            t[v].bas3 = 1;
        }else if(t[v].ans > 1){
            t[v].bit1 = 1;
            t[v].bas3 = 0;
        }else{
            t[v].bit1 = 0;
            t[v].bas3 = 0;
        }
        t[v].ok = 1;
    }else{
        int m = (l + r) / 2;
        if(m < pos){
            upd(2*v + 1, m + 1, r, pos);
        }else{
            upd(2*v, l, m, pos);
        }
        t[v].ans = t[v].bit1 = t[v].bas3 = t[v].ok = 0;
        int l2 = r - m;
        t[v].ans = 0;
        t[v].ans = (t[v].ans + t[2*v].ans*pw[l2][0]%mod)%mod;
        t[v].ans = (t[v].ans - (t[2*v].bit1*pw[l2][2]%mod) + mod)%mod;
        g(t[v].ans);
        t[v].ans = (t[v].ans + t[2*v].ok*t[2*v + 1].ans%mod)%mod;
        t[v].ans = (t[v].ans - (t[2*v].ok*(s[m] == '1')*t[2*v + 1].bas3%mod) + mod)%mod;
        g(t[v].ans);

        if(s[l] == '3'){
            t[v].bas3 = (t[v].ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod;
            g(t[v].bas3);
            t[v].bas3 %= mod;
        }else if(s[l] >= '4'){
            t[v].bas3 = pw[r - l][0];
        }else{
            t[v].bas3 = 0;
        }

        t[v].bit1 = 0;
        t[v].bit1 = (t[v].bit1 + t[2*v].ans*dp[0][l2][1]%mod)%mod;
        t[v].bit1 = (t[v].bit1 - t[2*v].bit1*dp[2][l2][1]%mod + mod)%mod;
        g(t[v].bit1);
        
        t[v].bit1 += t[2*v].ok*t[2*v + 1].bit1%mod;
        t[v].bit1 %= mod;

        if(s[m] == '1'){
            if(s[m + 1] > '3'){
                t[v].bit1 = (t[v].bit1 - t[2*v].ok*dp[2][r - m][1]%mod + mod)%mod;
                g(t[v].bit1);
            }else if(s[m + 1] == '3'){
                t[v].bit1 = (t[v].bit1 - t[2*v].ok*(t[2*v + 1].bit1 - 2*dp[0][r - m - 1][1]%mod - dp[1][r - m][1] + 2*mod)%mod + mod)%mod;
                g(t[v].bit1);
            }
        }
        t[v].ok = 0;

        if(s[m] == '1' && s[m + 1] == '3'){
            t[v].ok = 0;
        }else{
            t[v].ok = (t[2*v].ok && t[2*v + 1].ok);
        }
    }
}

node que(int v, int tl, int tr, int l, int r){
    if(l > r){
        node a = {-1, -1, -1, 0};
        return a;
    }else if(l == tl && r == tr){
        return t[v];
    }else{
        int tm = (tl + tr) / 2;
        node left = que(2*v, tl, tm, l, min(tm, r)),
             right = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r);
        if(r <= tm){
            return left;
        }else if(l >= tm + 1){
            return right;
        }else{
            node res;
            int l2 = r - tm;
            res.ans = 0;
            res.ans = (res.ans + left.ans*pw[l2][0]%mod)%mod;
            res.ans = (res.ans - (left.bit1*pw[l2][2]%mod) + mod)%mod;
            g(res.ans);

            res.ans = (res.ans + left.ok*right.ans%mod)%mod;
            res.ans = (res.ans - (left.ok*(s[tm] == '1')*right.bas3%mod) + mod)%mod;
            g(res.ans);

            if(s[l] == '3'){
                res.bas3 = (res.ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod;
                g(res.bas3);
                res.bas3 %= mod;
            }else if(s[l] >= '4'){
                res.bas3 = pw[r - l][0];
            }else{
                res.bas3 = 0;
            }

            res.bit1 = 0;
            res.bit1 = (res.bit1 + left.ans*dp[0][l2][1]%mod)%mod;
            res.bit1 = (res.bit1 - left.bit1*dp[2][l2][1]%mod + mod)%mod;
            g(res.bit1);
            res.bit1 += left.ok*right.bit1%mod;
            res.bit1 %= mod;

            if(s[tm] == '1'){
                if(s[tm + 1] > '3'){
                    res.bit1 = (res.bit1 - left.ok*dp[2][r - tm][1]%mod + mod)%mod;
                }else if(s[tm + 1] == '3'){
                    res.bit1 = (res.bit1 - left.ok*(right.bit1 - 2*dp[0][r - tm - 1][1]%mod - dp[1][r - tm][1] + 2*mod)%mod + mod)%mod;
                }
                g(res.bit1);
            }


            if(s[tm] == '1' && s[tm + 1] == '3'){
                res.ok = 0;
            }else{
                res.ok = (left.ok && right.ok);
            }
            return res;
        }
    }



}






int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>q;
    pw[0][0] = 0;
    dp[0][1][0] = 8;
    dp[0][1][1] = 1;
    dp[0][1][2] = 1;
    pw[1][0] = 10;
    for(int i = 2; i < MAXN ; i++){
        dp[0][i][0] = (dp[0][i - 1][0] + dp[0][i - 1][1] + dp[0][i - 1][2])%mod*8%mod;
        dp[0][i][1] = (dp[0][i - 1][0] + dp[0][i - 1][1] + dp[0][i - 1][2])%mod;
        dp[0][i][2] = (dp[0][i - 1][0] + dp[0][i - 1][2])%mod;
        pw[i][0] = (dp[0][i][0] + dp[0][i][1] + dp[0][i][2])%mod;
    }
    pw[0][1] = 0;
    dp[1][1][1] = 1;
    pw[1][1] = 1;
    for(int i = 2; i < MAXN ; i++){
        dp[1][i][0] = (dp[1][i - 1][0] + dp[1][i - 1][1] + dp[1][i - 1][2])%mod*8 % mod;
        dp[1][i][1] = (dp[1][i - 1][0] + dp[1][i - 1][1] + dp[1][i - 1][2])%mod;
        dp[1][i][2] = (dp[1][i - 1][0] + dp[1][i - 1][2])%mod;
        pw[i][1] = (dp[1][i][0] + dp[1][i][1] + dp[1][i][2])%mod;
    }

    pw[0][2] = 0;
    dp[2][1][2] = 1;
    pw[1][2] = 1;
    for(int i = 2; i < MAXN ; i++){
        dp[2][i][0] = (dp[2][i - 1][0] + dp[2][i - 1][1] + dp[2][i - 1][2])%mod*8% mod;
        dp[2][i][1] = (dp[2][i - 1][0] + dp[2][i - 1][1] + dp[2][i - 1][2])%mod;
        dp[2][i][2] = (dp[2][i - 1][0] + dp[2][i - 1][2])%mod;
        pw[i][2] = (dp[2][i][0] + dp[2][i][1] + dp[2][i][2])%mod;
    }
    cin>>s;

    build(1, 0, n - 1);
    node cr = que(1, 0, n - 1, 0, n - 1);

    cout<<(cr.ans + cr.ok)%mod<<endl;

    while(q--){
        int type;
        cin>>type;
        if(type == 1){
            int l, r;
            cin>>l>>r;
            
            node cr = que(1, 0, n - 1, l - 1, r - 1);
            cout<<(cr.ans + cr.ok)%mod<<endl;
        }else{
            int idx;
            char val;
            cin>>idx>>val;
            idx--;

            s[idx] = val;
            upd(1, 0, n - 1, idx);
        }
    }



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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