Submission #480130

#	Time	Username	Problem	Language	Result	Execution time	Memory
480130		nicolaalexandra	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	62 ms	16284 KiB

lucky

#include <bits/stdc++.h>
#define DIM 100010
#define MOD 1000000007
using namespace std;

long long dp[DIM];
int v[DIM];
char s[DIM];
int n,q,i,x,y,tip;

struct segment_tree{
    long long cnt; /// cate am in total
    long long cnt1; /// cate se termina cu 1
    long long cnt3; /// cate incep cu 3
    long long cnt31; /// cate incep cu 3 si se termina cu 1
    int ok,ok1,ok3,ok31; /// inf strict despre intervalul curent
    int sz; /// nr de cifre
} aint[DIM*4];


segment_tree update_nod (segment_tree fiu_st, segment_tree fiu_dr){

    segment_tree nod;

    nod.sz = fiu_st.sz + fiu_dr.sz;
    nod.ok = nod.ok1 = nod.ok3 = nod.ok31 = 0;
    if (!(fiu_st.ok1 && fiu_dr.ok3)){

        if (fiu_st.ok && fiu_dr.ok)
            nod.ok = 1;
        if (fiu_st.ok && fiu_dr.ok1)
            nod.ok1 = 1;
        if (fiu_st.ok3 && fiu_dr.ok)
            nod.ok3 = 1;
        if (fiu_st.ok3 && fiu_dr.ok1)
            nod.ok31 = 1;
    }

    /// mai mic strict stanga + orice in dreapta
    nod.cnt = (fiu_st.cnt - fiu_st.ok + MOD) * dp[fiu_dr.sz] % MOD;
    /// egal stanga, mai mic sau egal in dreapta
    nod.cnt = (nod.cnt + fiu_dr.cnt * fiu_st.ok) % MOD;

    nod.cnt = (nod.cnt - fiu_dr.cnt3 * fiu_st.ok1 % MOD + MOD) % MOD;
    nod.cnt = (nod.cnt - (fiu_st.cnt1 - fiu_st.ok1) * dp[ fiu_dr.sz - 1] % MOD + MOD) % MOD;


    nod.cnt1 = (fiu_st.cnt - fiu_st.ok + MOD) * dp[fiu_dr.sz - 1] % MOD;
    nod.cnt1 = (nod.cnt1 + fiu_dr.cnt1 * fiu_st.ok % MOD) % MOD;

    nod.cnt1 = (nod.cnt1 - (fiu_st.cnt1 - fiu_st.ok1) * dp[ fiu_dr.sz - 2 ] % MOD + MOD) % MOD;
    nod.cnt1 = (nod.cnt1 - fiu_st.ok1 * fiu_dr.cnt31 % MOD + MOD) % MOD;


    nod.cnt3 = (fiu_st.cnt3 - fiu_st.ok3 + MOD) * dp[fiu_dr.sz] % MOD;
    nod.cnt3 = (nod.cnt3 + fiu_dr.cnt * fiu_st.ok3 % MOD) % MOD;

    nod.cnt3 = (nod.cnt3 - (fiu_st.cnt31 - fiu_st.ok31) * dp[fiu_dr.sz-1] % MOD + MOD) % MOD;
    nod.cnt3 = (nod.cnt3 - fiu_st.ok31 * fiu_dr.cnt3 % MOD + MOD) % MOD;


    nod.cnt31 = (fiu_st.cnt3 - fiu_st.ok3 + MOD) * dp[fiu_dr.sz - 1] % MOD;
    nod.cnt31 = (nod.cnt31 + fiu_st.ok3 * fiu_dr.cnt1 % MOD) % MOD;

    nod.cnt31 = (nod.cnt31 - (fiu_st.cnt31 - fiu_st.ok31) * dp[fiu_dr.sz - 2] % MOD + MOD) % MOD;
    nod.cnt31 = (nod.cnt31 - fiu_st.ok31 * fiu_dr.cnt31 % MOD + MOD) % MOD;


    return nod;
}

void update_digit (int nod, int val){
    aint[nod].cnt = val+1;
    aint[nod].sz = 1;

    aint[nod].cnt1 = aint[nod].cnt3 = 1;
    if (val < 1)
        aint[nod].cnt1 = 0;
    if (val < 3)
        aint[nod].cnt3 = 0;

    aint[nod].cnt31 = 0;


    aint[nod].ok = 1, aint[nod].ok1 = aint[nod].ok3 = aint[nod].ok31 = 0;
    if (val == 1)
        aint[nod].cnt1 = aint[nod].ok1 = 1;
    if (val == 3)
        aint[nod].cnt3 = aint[nod].ok3 = 1;

}

void build (int nod, int st, int dr){
    if (st == dr){
        update_digit (nod,v[st]);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    aint[nod] = update_nod(aint[nod<<1],aint[(nod<<1)|1]);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        update_digit(nod,val);
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = update_nod(aint[nod<<1],aint[(nod<<1)|1]);
}

segment_tree query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y)
        return aint[nod];

    int mid = (st+dr)>>1;

    if (x > mid)
        return query ((nod<<1)|1,mid+1,dr,x,y);
    else {
        if (y <= mid)
            return query (nod<<1,st,mid,x,y);
        else return update_nod (query(nod<<1,st,mid,x,y),query((nod<<1)|1,mid+1,dr,x,y));
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>q;
    cin>>s+1;
    for (i=1;i<=n;i++)
        v[i] = s[i] - '0';

    /// dp[i] - cate nr bune de i cifre exista
    dp[0] = 1, dp[1] = 10;
    for (i=2;i<=n;i++)
        dp[i] = (dp[i-1] * 10 % MOD - dp[i-2] + MOD) % MOD;

    build (1,1,n);

    cout<<aint[1].cnt<<"\n";

    for (;q--;){
        cin>>tip>>x>>y;
        if (tip == 1)
            cout<<query (1,1,n,x,y).cnt<<"\n";
        else update (1,1,n,x,y);
    }

    return 0;
}

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:139:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |     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