oj.uz

Submission #480290

# Submission time Handle Problem Language Result Execution time Memory
480290 2021-10-15T14:13:24 Z Tenis0206 Lucky Numbers (RMI19_lucky) C++11
28 / 100
 58 ms 70800 KB 
#include <bits/stdc++.h>
#define int long long

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.val1 % 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.valmic1 % 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(qa<=mij && qb<=mij)
    {
        return rez1;
    }
    if(qa>mij && qb>mij)
    {
        return rez2;
    }
    return Merge(rez1,rez2);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  //  freopen("nr.in","r",stdin);
  //  freopen("nr.out","w",stdout);
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70680 KB Output is correct
2 Correct 34 ms 70740 KB Output is correct
3 Correct 39 ms 70752 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70680 KB Output is correct
2 Correct 34 ms 70740 KB Output is correct
3 Correct 39 ms 70752 KB Output is correct
4 Correct 35 ms 70688 KB Output is correct
5 Correct 44 ms 70724 KB Output is correct
6 Correct 35 ms 70724 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70680 KB Output is correct
2 Correct 34 ms 70740 KB Output is correct
3 Correct 39 ms 70752 KB Output is correct
4 Correct 35 ms 70688 KB Output is correct
5 Correct 44 ms 70724 KB Output is correct
6 Correct 35 ms 70724 KB Output is correct
7 Incorrect 58 ms 70800 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70680 KB Output is correct
2 Correct 34 ms 70740 KB Output is correct
3 Correct 39 ms 70752 KB Output is correct
4 Correct 35 ms 70688 KB Output is correct
5 Correct 44 ms 70724 KB Output is correct
6 Correct 35 ms 70724 KB Output is correct
7 Incorrect 58 ms 70800 KB Output isn't correct
8 Halted 0 ms 0 KB -