oj.uz

Submission #1093291

# Submission time Handle Problem Language Result Execution time Memory
1093291 2024-09-26T13:06:00 Z alexdd Lucky Numbers (RMI19_lucky) C++17
100 / 100
 158 ms 26192 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
struct node
{
    int cnt[2][2];//daca e egal si il face mai mic acum
    int deja[2][2];//daca e deja mai mic
    int lun;
    bool has13;
    int vle,vri;
};
node combine(node x, node y)
{
    if(x.lun==-1)
        return y;
    if(y.lun==-1)
        return x;
    ///1 - periculos
    node aux;
    aux.lun = x.lun + y.lun;
    aux.vle = x.vle;
    aux.vri = y.vri;
    aux.has13 = (x.has13 | y.has13);
    if(x.vri==1 && y.vle==3) aux.has13=1;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            aux.cnt[i][j]=aux.deja[i][j]=0;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            aux.deja[i][j] += (x.deja[i][0]*(y.deja[0][j]+y.deja[1][j]) + x.deja[i][1]*y.deja[0][j])%MOD;

            aux.cnt[i][j] += (x.cnt[i][0]*(y.deja[0][j]+y.deja[1][j]) + x.cnt[i][1]*y.deja[0][j])%MOD;

        }
        if(!x.has13)
        {
            if(x.vle==3)
            {
                if(x.vri==1)
                    aux.cnt[1][i] += y.cnt[0][i];
                else
                    aux.cnt[1][i] += y.cnt[0][i] + y.cnt[1][i];
            }
            else
            {
                if(x.vri==1)
                    aux.cnt[0][i] += y.cnt[0][i];
                else
                    aux.cnt[0][i] += y.cnt[0][i] + y.cnt[1][i];
            }
        }
    }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            aux.cnt[i][j]%=MOD, aux.deja[i][j]%=MOD;
    return aux;
}
node fa_nod(int cif)
{
    node aux;

    aux.lun = 1;
    aux.vle = aux.vri = cif;
    aux.has13 = 0;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            aux.cnt[i][j] = aux.deja[i][j] = 0;

    for(int i=0;i<10;i++)
    {
        if(i==1)
            aux.deja[0][1]++;
        else if(i==3)
            aux.deja[1][0]++;
        else
            aux.deja[0][0]++;
        if(i < cif)
        {
            if(i==1)
                aux.cnt[0][1]++;
            else if(i==3)
                aux.cnt[1][0]++;
            else
                aux.cnt[0][0]++;
        }
    }
    return aux;
}
node emp = {{{-1,-1},{-1,-1}},{{-1,-1},{-1,-1}},-1,0,-1,-1};

node aint[270000];
void upd(int nod, int st, int dr, int poz, int newv)
{
    if(st==dr)
    {
        aint[nod] = fa_nod(newv);
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return emp;
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int n,q;
int a[100005];
void afis(int x, int y)
{
    node aux = qry(1,1,n,x,y);
    int rez=0;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            rez = (rez + aux.cnt[i][j])%MOD;
    if(!aux.has13) rez = (rez+1)%MOD;
    cout<<rez<<"\n";
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    char ch;
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        a[i] = ch-'0';
        upd(1,1,n,i,a[i]);
    }
    afis(1,n);
    int tip,x,y;
    while(q--)
    {
        cin>>tip>>x>>y;
        if(tip==1)
        {
            afis(x,y);
        }
        else
        {
            upd(1,1,n,x,y);
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2820 KB Output is correct
2 Correct 25 ms 4844 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2820 KB Output is correct
2 Correct 25 ms 4844 KB Output is correct
3 Correct 118 ms 25936 KB Output is correct
4 Correct 116 ms 25940 KB Output is correct
5 Correct 133 ms 25980 KB Output is correct
6 Correct 145 ms 26192 KB Output is correct
7 Correct 142 ms 25988 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 18 ms 2820 KB Output is correct
8 Correct 25 ms 4844 KB Output is correct
9 Correct 17 ms 2648 KB Output is correct
10 Correct 24 ms 4696 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 18 ms 2820 KB Output is correct
8 Correct 25 ms 4844 KB Output is correct
9 Correct 118 ms 25936 KB Output is correct
10 Correct 116 ms 25940 KB Output is correct
11 Correct 133 ms 25980 KB Output is correct
12 Correct 145 ms 26192 KB Output is correct
13 Correct 142 ms 25988 KB Output is correct
14 Correct 17 ms 2648 KB Output is correct
15 Correct 24 ms 4696 KB Output is correct
16 Correct 120 ms 25940 KB Output is correct
17 Correct 115 ms 25976 KB Output is correct
18 Correct 134 ms 25940 KB Output is correct
19 Correct 151 ms 25940 KB Output is correct
20 Correct 158 ms 25940 KB Output is correct