Submission #480297

#	Time	Username	Problem	Language	Result	Execution time	Memory
480297		Tenis0206	Lucky Numbers (RMI19_lucky)	C++11	100 / 100	193 ms	36036 KiB

lucky

#include <bits/stdc++.h>

using namespace std;

const int Mod = 1e9 + 7;

struct node
{
    int val, val1, val3, val31;
    int valmic, valmic1, valmic3, valmic31;
    bool ok, ok1, ok3, ok31;
    node()
    {
        val = val1 = val3 = val31 = 0;
        valmic = valmic1 = valmic3 = valmic31 = 0;
        ok = ok1 = ok3 = ok31 = false;
    }
};

int n,q,v[100005];

node ai[1000005];

node Merge(node a, node b)
{
    node rez;
    rez.val = (1LL * a.val * b.val % Mod - 1LL * a.val1 * b.val3 % Mod + Mod) % Mod;
    rez.val1 = (1LL * a.val * b.val1 % Mod - 1LL * a.val1 * b.val31 % Mod + Mod) % Mod;
    rez.val3 = (1LL * a.val3 * b.val % Mod - 1LL * a.val31 * b.val3 % Mod + Mod) % Mod;
    rez.val31 = (1LL * a.val3 * b.val1 % Mod - 1LL * a.val31 * b.val31 % Mod + Mod) % Mod;
    rez.valmic = ((1LL * a.valmic * b.val % Mod - 1LL * a.valmic1 * b.val3 % Mod + Mod) % Mod + (1LL * a.ok * b.valmic % Mod - 1LL * a.ok1 * b.valmic3 % Mod + Mod) % Mod) % Mod;
    rez.valmic1 = ((1LL * a.valmic * b.val1 % Mod - 1LL * a.valmic1 * b.val31 % Mod + Mod) % Mod + (1LL * a.ok * b.valmic1 % Mod - 1LL * a.ok1 * b.valmic31 % Mod + Mod) % Mod) % Mod;
    rez.valmic3 = ((1LL * a.valmic3 * b.val % Mod - 1LL * a.valmic31 * b.val3 % Mod + Mod) % Mod + (1LL * a.ok3 * b.valmic % Mod - 1LL * a.ok31 * b.valmic3 % Mod + Mod) % Mod) % Mod;
    rez.valmic31 = ((1LL * a.valmic3 * b.val1 % Mod - 1LL * a.valmic31 * b.val31 % Mod + Mod) % Mod + (1LL * a.ok3 * b.valmic1 % Mod - 1LL * a.ok31 * b.valmic31 % Mod + Mod) % Mod) % Mod;
    rez.ok = (a.ok & b.ok & ((!a.ok1)|(!b.ok3)));
    rez.ok1 = (rez.ok & b.ok1);
    rez.ok3 = (rez.ok & a.ok3);
    rez.ok31 = (rez.ok & b.ok1 & a.ok3);
    return rez;
}

node Init(int val)
{
    node rez;
    rez.val = 10;
    rez.val1 = 1;
    rez.val3 = 1;
    rez.val31 = 0;
    rez.valmic = val;
    rez.valmic1 = (1<val);
    rez.valmic3 = (3<val);
    rez.valmic31 = 0;
    rez.ok = true;
    rez.ok1 = (val==1);
    rez.ok3 = (val==3);
    rez.ok31 = false;
    return rez;
}

void update(int poz, int val, int nod, int a, int b)
{
    if(a==b)
    {
        ai[nod] = Init(val);
        return;
    }
    int mij = (a+b)>>1;
    if(poz<=mij)
    {
        update(poz,val,nod*2,a,mij);
    }
    else
    {
        update(poz,val,nod*2+1,mij+1,b);
    }
    ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
}

node query(int qa, int qb, int nod, int a, int b)
{
    if(qa<=a && qb>=b)
    {
        return ai[nod];
    }
    int mij = (a+b)>>1;
    node rez1, rez2;
    if(qa<=mij)
    {
        rez1 = query(qa,qb,nod*2,a,mij);
    }
    if(qb>mij)
    {
        rez2 = query(qa,qb,nod*2+1,mij+1,b);
    }
    if(qb<=mij)
    {
        return rez1;
    }
    if(qa>mij)
    {
        return rez2;
    }
    return Merge(rez1,rez2);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    cin.get();
    for(int i=1;i<=n;i++)
    {
        char ch;
        cin.get(ch);
        v[i] = ch - '0';
        update(i,v[i],1,1,n);
    }
    cout<<(ai[1].valmic + ai[1].ok) % Mod<<'\n';
    for(int i=1;i<=q;i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int l,r;
            cin>>l>>r;
            node rez = query(l,r,1,1,n);
            cout<<(rez.valmic + rez.ok) % Mod<<'\n';
        }
        else
        {
            int poz,val;
            cin>>poz>>val;
            update(poz,val,1,1,n);
        }
    }
    return 0;
}

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