oj.uz

Submission #200646

# Submission time Handle Problem Language Result Execution time Memory
200646 2020-02-07T19:16:30 Z nicolaalexandra Lucky Numbers (RMI19_lucky) C++14
28 / 100
 42 ms 2296 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define MOD 1000000007
using namespace std;
int v[DIM];
int n,q,c,x,y,i,_first;
long long sol0,sol1,sol3,sol_fin0,sol_fin1,sol_fin3;
char ch;
struct segment_tree{
    long long s00, s01, s03;
    long long s10, s11, s13;
    long long s30, s31, s33;
};
segment_tree aint[DIM*4], dp[DIM];


void update_node (int nod, int st, int dr){

    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    if (dr - st == 1){
        aint[nod].s00 = 1LL*aint[fiu_st].s00 * dp[1].s00 % MOD;
        aint[nod].s01 = 1LL*aint[fiu_st].s00 * dp[1].s11 % MOD;
        aint[nod].s03 = 1LL*aint[fiu_st].s00 * dp[1].s33 % MOD;
        if (v[st] != 1 && v[st] != 3){
            aint[nod].s00 = (aint[nod].s00 + aint[fiu_dr].s00) % MOD;
            aint[nod].s01 = (aint[nod].s01 + aint[fiu_dr].s11) % MOD;
            aint[nod].s03 = (aint[nod].s03 + aint[fiu_dr].s33) % MOD;
        }


        aint[nod].s10 = 1LL * aint[fiu_st].s11 * dp[1].s00 % MOD;
        aint[nod].s11 = 1LL * aint[fiu_st].s11 * dp[1].s11 % MOD;
        if (v[st] == 1){
            aint[nod].s10 = (aint[nod].s10 + aint[fiu_dr].s00) % MOD;
            aint[nod].s11 = (aint[nod].s11 + aint[fiu_dr].s11) % MOD;
        }

        aint[nod].s13 = 0;

        aint[nod].s30 = 1LL*aint[fiu_st].s33 * dp[1].s00 % MOD;
        aint[nod].s31 = 1LL*aint[fiu_st].s33 * dp[1].s11 % MOD;
        aint[nod].s33 = 1LL*aint[fiu_st].s33 * dp[1].s33 % MOD;
        if (v[st] == 3){
            aint[nod].s30 = (aint[nod].s30 + aint[fiu_dr].s00) % MOD;
            aint[nod].s31 = (aint[nod].s31 + aint[fiu_dr].s11) % MOD;
            aint[nod].s33 = (aint[nod].s33 + aint[fiu_dr].s33) % MOD;
        }

        return;
    }
    int mid = (st+dr)>>1;
    int nr = dr-mid;
    /// stare 00
    int sum = 0;
    sum = (sum + dp[nr].s00) % MOD;
    sum = (sum + dp[nr].s10) % MOD;
    sum = (sum + dp[nr].s30) % MOD;

    aint[nod].s00 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD;
    aint[nod].s00 = (aint[nod].s00 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD;
    /// la cazul asta nu am voie cu 3
    int val = sum - dp[nr].s30;
    if (val < 0)
        val += MOD;
    aint[nod].s00 = (aint[nod].s00 + 1LL*aint[fiu_st].s01*val % MOD) % MOD;


    /// stare 01
    sum = 0;
    sum = (sum + dp[nr].s01) % MOD;
    sum = (sum + dp[nr].s11) % MOD;
    sum = (sum + dp[nr].s31) % MOD;

    aint[nod].s01 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD;
    aint[nod].s01 = (aint[nod].s01 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD;
    val = sum - dp[nr].s31;
    if (val < 0)
        val += MOD;
    aint[nod].s01 = (aint[nod].s01 + 1LL*aint[fiu_st].s01*val % MOD) % MOD;


    /// stare 03
    sum = 0;
    sum = (sum + dp[nr].s03) % MOD;
    sum = (sum + dp[nr].s13) % MOD;
    sum = (sum + dp[nr].s33) % MOD;
    aint[nod].s03 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD;
    aint[nod].s03 = (aint[nod].s03 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD;
    val = sum - dp[nr].s33;
    if (val < 0)
        val += MOD;
    aint[nod].s03 = (aint[nod].s03 + 1LL*aint[fiu_st].s01*val % MOD) % MOD;

    /// stare 10
    sum = 0;
    sum = (sum + dp[nr].s00) % MOD;
    sum = (sum + dp[nr].s10) % MOD;
    sum = (sum + dp[nr].s30) % MOD;
    aint[nod].s10 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD;
    aint[nod].s10 = (aint[nod].s10 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD;
    val = sum - dp[nr].s30;
    if (val < 0)
        val += MOD;
    aint[nod].s10 = (aint[nod].s10 + 1LL*aint[fiu_st].s11*val%MOD) % MOD;

    /// stare 11
    sum = 0;
    sum = (sum + dp[nr].s01) % MOD;
    sum = (sum + dp[nr].s11) % MOD;
    sum = (sum + dp[nr].s31) % MOD;
    aint[nod].s11 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD;
    aint[nod].s11 = (aint[nod].s11 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD;
    val = sum - dp[nr].s31;
    if (val < 0)
        val += MOD;
    aint[nod].s11 = (aint[nod].s11 + 1LL*aint[fiu_st].s11*val%MOD) % MOD;

    /// stare 13
    sum = 0;
    sum = (sum + dp[nr].s03) % MOD;
    sum = (sum + dp[nr].s13) % MOD;
    sum = (sum + dp[nr].s33) % MOD;
    aint[nod].s13 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD;
    aint[nod].s13 = (aint[nod].s13 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD;
    val = sum - dp[nr].s33;
    if (val < 0)
        val += MOD;
    aint[nod].s13 = (aint[nod].s13 + 1LL*aint[fiu_st].s11*val%MOD) % MOD;


    /// stare 30
    sum = 0;
    sum = (sum + dp[nr].s00) % MOD;
    sum = (sum + dp[nr].s10) % MOD;
    sum = (sum + dp[nr].s30) % MOD;
    aint[nod].s30 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD;
    aint[nod].s30 = (aint[nod].s30 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD;
    val = sum - dp[nr].s30;
    if (val < 0)
        val += MOD;
    aint[nod].s30 = (aint[nod].s30 + 1LL*aint[fiu_st].s31*val%MOD) % MOD;


    /// stare 31
    sum = 0;
    sum = (sum + dp[nr].s01) % MOD;
    sum = (sum + dp[nr].s11) % MOD;
    sum = (sum + dp[nr].s31) % MOD;
    aint[nod].s31 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD;
    aint[nod].s31 = (aint[nod].s31 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD;
    val = sum - dp[nr].s31;
    if (val < 0)
        val += MOD;
    aint[nod].s31 = (aint[nod].s31 + 1LL*aint[fiu_st].s31*val%MOD) % MOD;


    /// stare 33
    sum = 0;
    sum = (sum + dp[nr].s03) % MOD;
    sum = (sum + dp[nr].s13) % MOD;
    sum = (sum + dp[nr].s33) % MOD;
    aint[nod].s33 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD;
    aint[nod].s33 = (aint[nod].s33 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD;
    val = sum - dp[nr].s33;
    if (val < 0)
        val += MOD;
    aint[nod].s33 = (aint[nod].s33 + 1LL*aint[fiu_st].s31*val%MOD) % MOD;



    /// acum mai ramane cazul in care pastrez fiul stang integral asa cum e si
    /// trebuie sa adaug de la fiul drept pt toate starile

    /// singurul caz special e cand am pe mid 1
    sum = (aint[fiu_dr].s00 + aint[fiu_dr].s01 + aint[fiu_dr].s03) % MOD;
    sum = (sum + aint[fiu_dr].s10 + aint[fiu_dr].s11 + aint[fiu_dr].s13) % MOD;
    sum = (sum + aint[fiu_dr].s30 + aint[fiu_dr].s31 + aint[fiu_dr].s33) % MOD;
    if (v[st] == 1){
        aint[nod].s10 = (aint[nod].s10 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD;
        aint[nod].s11 = (aint[nod].s11 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD;
        aint[nod].s13 = (aint[nod].s13 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD;
        if (v[mid] == 1){
            /// trebuie sa mai scad cv
            aint[nod].s10 -= aint[fiu_dr].s30;
            if (aint[nod].s10 < 0) aint[nod].s10 += MOD;
            aint[nod].s11 -= aint[fiu_dr].s31;
            if (aint[nod].s11 < 0) aint[nod].s11 += MOD;
            aint[nod].s13 -= aint[fiu_dr].s33;
            if (aint[nod].s13 < 0) aint[nod].s13 += MOD;
        }
    } else {
        if (v[st] == 3){
            aint[nod].s30 = (aint[nod].s30 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD;
            aint[nod].s31 = (aint[nod].s31 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD;
            aint[nod].s33 = (aint[nod].s33 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD;
            if (v[mid] == 1){
                /// trebuie sa mai scad cv
                aint[nod].s30 -= aint[fiu_dr].s30;
                if (aint[nod].s30 < 0) aint[nod].s30 += MOD;
                aint[nod].s31 -= aint[fiu_dr].s31;
                if (aint[nod].s31 < 0) aint[nod].s31 += MOD;
                aint[nod].s33 -= aint[fiu_dr].s33;
                if (aint[nod].s33 < 0) aint[nod].s33 += MOD;
            }

        } else { /// altceva => 0
            aint[nod].s00 = (aint[nod].s00 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD;
            aint[nod].s01 = (aint[nod].s01 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD;
            aint[nod].s03 = (aint[nod].s03 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD;
            if (v[mid] == 1){
                /// trebuie sa mai scad cv
                aint[nod].s00 -= aint[fiu_dr].s30;
                if (aint[nod].s00 < 0) aint[nod].s00 += MOD;
                aint[nod].s01 -= aint[fiu_dr].s31;
                if (aint[nod].s01 < 0) aint[nod].s01 += MOD;
                aint[nod].s03 -= aint[fiu_dr].s33;
                if (aint[nod].s03 < 0) aint[nod].s03 += MOD;
            }
        }
    }
}

void build (int nod, int st, int dr){
    if (st == dr){
        if (v[st] == 0)
            return;

        if (v[st] == 1){
            aint[nod].s00 = 1;
            return;
        }
        if (v[st] == 2){
            aint[nod].s00 = 1, aint[nod].s11 = 1;
            return;
        }
        if (v[st] == 3){
            aint[nod].s00 = 2, aint[nod].s11 = 1;
            return;
        }
        aint[nod].s11 = aint[nod].s33 = 1;
        aint[nod].s00 = v[st] - 2;

        return;
    }

    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    update_node (nod,st,dr);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].s00 = aint[nod].s11 = aint[nod].s33 = 0;
        if (val == 0)
            return;

        if (val == 1){
            aint[nod].s00 = 1;
            return;
        }
        if (val == 2){
            aint[nod].s00 = 1, aint[nod].s11 = 1;
            return;
        }
        if (val == 3){
            aint[nod].s00 = 2, aint[nod].s11 = 1;
            return;
        }
        aint[nod].s11 = aint[nod].s33 = 1;
        aint[nod].s00 = val - 2;
        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);

    update_node (nod,st,dr);
}
void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        /// vreau sa adaug intervalul asta la solutie
        long long sol_aux0 = 0, sol_aux1 = 0, sol_aux3 = 0;
        int nr = dr-st+1; /// cate am dupa
        /// daca iau toate nr din intervalul asta mai mici, restul le completez cu dp
        if (!_first){
            _first = 1;
            sol0 = (aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD;
            sol1 = (aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD;
            sol3 = (aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD;
            sol_aux0 = sol0, sol_aux1 = sol1, sol_aux3 = sol3;
        } else {
            /// sol_aux0
            int sum = (dp[nr].s00 + dp[nr].s10 + dp[nr].s30) % MOD;
            sol_aux0 = (sol_aux0 + sol0 * sum % MOD) % MOD;
            sol_aux0 = (sol_aux0 + sol3 * sum % MOD) % MOD;
            sum -= dp[nr].s30;
            if (sum < 0)
                sum += MOD;
            sol_aux0 = (sol_aux0 + sol1 * sum % MOD) % MOD;
            /// sol_aux 1
            sum = (dp[nr].s01 + dp[nr].s11 + dp[nr].s31) % MOD;
            sol_aux1 = (sol_aux1 + sol0 * sum % MOD) % MOD;
            sol_aux1 = (sol_aux1 + sol3 * sum % MOD) % MOD;
            sum -= dp[nr].s31;
            if (sum < 0)
                sum += MOD;
            sol_aux1 = (sol_aux1 + sol1 * sum % MOD) % MOD;


            /// sol_aux3
            sum = (dp[nr].s03 + dp[nr].s13 + dp[nr].s33) % MOD;
            sol_aux3 = (sol_aux3 + sol0 * sum % MOD) % MOD;
            sol_aux3 = (sol_aux3 + sol3 * sum % MOD) % MOD;
            sum -= dp[nr].s33;
            if (sum < 0)
                sum += MOD;
            sol_aux3 = (sol_aux3 + sol1 * sum % MOD) % MOD;

            /// cazul cu egalitatatea -> trb sa iau doar valorile mai mici din intv asta

            sum = (aint[nod].s00 + aint[nod].s10 + aint[nod].s30) % MOD;
            if (v[st-1] == 1){
                sum -= aint[nod].s30;
                if (sum < 0)
                    sum += MOD;
                sol_aux0 = (sol_aux0 + sum) % MOD;
            } else sol_aux0 = (sol_aux0 + sum) % MOD;
            ///
            sum = (aint[nod].s01 + aint[nod].s11 + aint[nod].s31) % MOD;
            if (v[st-1] == 1){
                sum -= aint[nod].s31;
                if (sum < 0)
                    sum += MOD;
                sol_aux1 = (sol_aux1 + sum) % MOD;
            } else sol_aux1 = (sol_aux1 + sum) % MOD;
            ///
            sum = (aint[nod].s03 + aint[nod].s13 + aint[nod].s33) % MOD;
            if (v[st-1] == 1){
                sum -= aint[nod].s33;
                if (sum < 0)
                    sum += MOD;
                sol_aux3 = (sol_aux3 + sum) % MOD;
            } else sol_aux3 = (sol_aux3 + sum) % MOD;
            /*sol_aux0 = (sol_aux0 + 1LL*(sol0+1)*(aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD)%MOD;
            sol_aux0 = (sol_aux0 + 1LL*(sol3+1)*(aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD)%MOD;
            sol_aux0 = (sol_aux0 + 1LL*(sol1+1)*(aint[nod].s00 + aint[nod].s10)%MOD)%MOD;

            sol_aux1 = (sol_aux1 + 1LL*(sol0+1)*(aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD)%MOD;
            sol_aux1 = (sol_aux1 + 1LL*(sol3+1)*(aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD)%MOD;
            sol_aux1 = (sol_aux1 + 1LL*(sol1+1)*(aint[nod].s01 + aint[nod].s11)%MOD)%MOD;

            sol_aux3 = (sol_aux3 + 1LL*(sol0+1)*(aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD)%MOD;
            sol_aux3 = (sol_aux3 + 1LL*(sol3+1)*(aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD)%MOD;
            sol_aux3 = (sol_aux3 + 1LL*(sol1+1)*(aint[nod].s03 + aint[nod].s13)%MOD)%MOD;

            */

        }

        sol0 = sol_aux0;
        sol1 = sol_aux1;
        sol3 = sol_aux3;

        /*nr = 0;
        if (nr){

            sol_aux0 = sol_aux1 = sol_aux3 = 1;

            int sum = (dp[nr].s00 + dp[nr].s10 + dp[nr].s30) % MOD;
            sol_fin0 = (sol_fin0 + sol_aux0 * sum % MOD) % MOD;
            sol_fin0 = (sol_fin0 + sol_aux3 * sum % MOD) % MOD;
            if (v[dr] == 1){
                sum -= dp[nr].s30;
                if (sum < 0)
                    sum += MOD;
            }
            sol_fin0 = (sol_fin0 + sol_aux1 * sum % MOD) % MOD;

            sum = (dp[nr].s01 + dp[nr].s11 + dp[nr].s31) %  MOD;
            sol_fin1 = (sol_fin1 + sol_aux0 * sum % MOD) % MOD;
            sol_fin1 = (sol_fin1 + sol_aux3 * sum % MOD) % MOD;
            if (v[dr] == 1){
                sum -= dp[nr].s31;
                if (sum < 0)
                    sum += MOD;
            }
            sol_fin1 = (sol_fin1 + sol_aux1 * sum % MOD) % MOD;

            sum = (dp[nr].s03 + dp[nr].s13 + dp[nr].s33) % MOD;
            sol_fin3 = (sol_fin3 + sol_aux0 * sum % MOD) % MOD;
            sol_fin3 = (sol_fin3 + sol_aux3 * sum % MOD) % MOD;
            if (v[dr] == 1){
                sum -= dp[nr].s33;
                if (sum < 0)
                    sum += MOD;
            }
            sol_fin3 = (sol_fin3 + sol_aux1 * sum % MOD) % MOD;
        }*/


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

int main (){

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

    cin>>n>>q;

    for (i=1;i<=n;i++){
        cin>>ch;
        v[i] = ch - '0';
    }

    /// dp[i].stare - cate nr de i cifre pot forma care au starea stare
    dp[1].s11 = dp[1].s33 = 1;
    dp[1].s00 = 8;
    for (i=2;i<=n;i++){
        dp[i].s00 = 8 * (dp[i-1].s00 + dp[i-1].s01 + dp[i-1].s03) % MOD;
        dp[i].s01 = (dp[i-1].s00 + dp[i-1].s01 + dp[i-1].s03) % MOD;
        dp[i].s03 = (dp[i-1].s00 + dp[i-1].s03) % MOD;

        dp[i].s10 = 8 * (dp[i-1].s10 + dp[i-1].s11 + dp[i-1].s13) % MOD;
        dp[i].s11 = (dp[i-1].s10 + dp[i-1].s11 + dp[i-1].s13) % MOD;
        dp[i].s13 = (dp[i-1].s10 + dp[i-1].s13) % MOD;

        dp[i].s30 = 8 * (dp[i-1].s30 + dp[i-1].s31 + dp[i-1].s33) % MOD;
        dp[i].s31 = (dp[i-1].s30 + dp[i-1].s31 + dp[i-1].s33) % MOD;
        dp[i].s33 = (dp[i-1].s30 + dp[i-1].s33) % MOD;
    }

    build (1,1,n);
    sol0 = sol1 = sol3 = _first = 0;
    query(1,1,n,1,n);
    cout<<(sol0 + sol1 + sol3 + 1)%MOD<<"\n";
    /// aint[nod] - cate nr mai mici sau egale decat intervalul ala pot forma

    for (;q--;){
        cin>>c>>x>>y;
        if (c == 1){ /// query
            sol0 = sol1 = sol3 = _first = 0;
            sol_fin0 = 0, sol_fin1 = 0, sol_fin3 = 0;
            query (1,1,n,x,y);
            int sol = (sol0 + sol1 + sol3 + 1) % MOD;
            sol = (sol + sol_fin0 + sol_fin1 + sol_fin3) % MOD;
            cout<<sol<<"\n";
        } else {
            v[x] = y;
            update (1,1,n,x,y);
        }
    }


    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Incorrect 42 ms 2296 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Incorrect 42 ms 2296 KB Output isn't correct
8 Halted 0 ms 0 KB -