oj.uz

Submission #480297

# Submission time Handle Problem Language Result Execution time Memory
480297 2021-10-15T14:42:55 Z Tenis0206 Lucky Numbers (RMI19_lucky) C++11
100 / 100
 193 ms 36036 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 22 ms 35440 KB Output is correct
3 Correct 21 ms 35456 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 22 ms 35440 KB Output is correct
3 Correct 21 ms 35456 KB Output is correct
4 Correct 21 ms 35432 KB Output is correct
5 Correct 19 ms 35444 KB Output is correct
6 Correct 23 ms 35452 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35596 KB Output is correct
2 Correct 46 ms 35652 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35596 KB Output is correct
2 Correct 46 ms 35652 KB Output is correct
3 Correct 144 ms 35908 KB Output is correct
4 Correct 143 ms 35948 KB Output is correct
5 Correct 171 ms 35884 KB Output is correct
6 Correct 176 ms 36036 KB Output is correct
7 Correct 190 ms 35968 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 22 ms 35440 KB Output is correct
3 Correct 21 ms 35456 KB Output is correct
4 Correct 21 ms 35432 KB Output is correct
5 Correct 19 ms 35444 KB Output is correct
6 Correct 23 ms 35452 KB Output is correct
7 Correct 39 ms 35596 KB Output is correct
8 Correct 46 ms 35652 KB Output is correct
9 Correct 48 ms 35560 KB Output is correct
10 Correct 44 ms 35564 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 22 ms 35440 KB Output is correct
3 Correct 21 ms 35456 KB Output is correct
4 Correct 21 ms 35432 KB Output is correct
5 Correct 19 ms 35444 KB Output is correct
6 Correct 23 ms 35452 KB Output is correct
7 Correct 39 ms 35596 KB Output is correct
8 Correct 46 ms 35652 KB Output is correct
9 Correct 144 ms 35908 KB Output is correct
10 Correct 143 ms 35948 KB Output is correct
11 Correct 171 ms 35884 KB Output is correct
12 Correct 176 ms 36036 KB Output is correct
13 Correct 190 ms 35968 KB Output is correct
14 Correct 48 ms 35560 KB Output is correct
15 Correct 44 ms 35564 KB Output is correct
16 Correct 151 ms 35968 KB Output is correct
17 Correct 148 ms 35760 KB Output is correct
18 Correct 155 ms 35876 KB Output is correct
19 Correct 174 ms 35908 KB Output is correct
20 Correct 193 ms 35884 KB Output is correct