oj.uz

Submission #730201

# Submission time Handle Problem Language Result Execution time Memory
730201 2023-04-25T11:56:11 Z DJeniUp Lucky Numbers (RMI19_lucky) C++17
100 / 100
 84 ms 27980 KB 
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 100000000000007
#define eps 0.00000000001
//#define A ll(1e12)

ll n,m,a[N];

struct D{
    ll a[13];
}d[4*N];

D S(D x, D y){
    D ret;
    ret.a[1]=(x.a[1]*y.a[3]%MOD+x.a[2]*(y.a[3]+y.a[1])%MOD)%MOD;
    ret.a[2]=(x.a[1]*y.a[4]%MOD+x.a[2]*(y.a[4]+y.a[2])%MOD)%MOD;
    ret.a[3]=(x.a[3]*y.a[3]%MOD+x.a[4]*(y.a[3]+y.a[1])%MOD)%MOD;
    ret.a[4]=(x.a[3]*y.a[4]%MOD+x.a[4]*(y.a[4]+y.a[2])%MOD)%MOD;
    ret.a[5]=((x.a[1]*y.a[7]%MOD+x.a[2]*(y.a[7]+y.a[5])%MOD)%MOD+(x.a[5]*y.a[11]%MOD+x.a[6]*(y.a[11]+y.a[9])%MOD)%MOD)%MOD;
    ret.a[6]=((x.a[1]*y.a[8]%MOD+x.a[2]*(y.a[8]+y.a[6])%MOD)%MOD+(x.a[5]*y.a[12]%MOD+x.a[6]*(y.a[12]+y.a[10])%MOD)%MOD)%MOD;
    ret.a[7]=((x.a[3]*y.a[7]%MOD+x.a[4]*(y.a[7]+y.a[5])%MOD)%MOD+(x.a[7]*y.a[11]%MOD+x.a[8]*(y.a[11]+y.a[9])%MOD)%MOD)%MOD;
    ret.a[8]=((x.a[3]*y.a[8]%MOD+x.a[4]*(y.a[8]+y.a[6])%MOD)%MOD+(x.a[7]*y.a[12]%MOD+x.a[8]*(y.a[12]+y.a[10])%MOD)%MOD)%MOD;
    ret.a[9]=(x.a[9]*y.a[11]%MOD+x.a[10]*(y.a[11]+y.a[9])%MOD)%MOD;
    ret.a[10]=(x.a[9]*y.a[12]%MOD+x.a[10]*(y.a[12]+y.a[10])%MOD)%MOD;
    ret.a[11]=(x.a[11]*y.a[11]%MOD+x.a[12]*(y.a[11]+y.a[9])%MOD)%MOD;
    ret.a[12]=(x.a[11]*y.a[12]%MOD+x.a[12]*(y.a[12]+y.a[10])%MOD)%MOD;
    return ret;
}

void BT(ll x,ll l,ll r){
    if(l==r){
        d[x].a[1]=0;
        if(a[l]==3)d[x].a[2]=1;
        else d[x].a[2]=0;
        if(a[l]==1)d[x].a[3]=1;
        else d[x].a[3]=0;
        if(a[l]!=1 && a[l]!=3)d[x].a[4]=1;
        else d[x].a[4]=0;
        d[x].a[5]=0;
        if(a[l]>3)d[x].a[6]=1;
        else d[x].a[6]=0;
        if(a[l]>1)d[x].a[7]=1;
        else d[x].a[7]=0;
        if(a[l]>3)d[x].a[8]=a[l]-2;
        else if(a[l]>1)d[x].a[8]=a[l]-1;
        else d[x].a[8]=a[l];
        d[x].a[9]=0;
        d[x].a[10]=1;
        d[x].a[11]=1;
        d[x].a[12]=8;
       // cout<<x<<" "<<l<<" "<<r<<" "<<d[x].a[1]+d[x].a[2]+d[x].a[3]+d[x].a[4]+d[x].a[5]+d[x].a[6]+d[x].a[7]+d[x].a[8]<<endl;
       // cout<<d[x].a[1]<<" "<<d[x].a[2]<<" "<<d[x].a[3]<<" "<<d[x].a[4]<<" "<<d[x].a[5]<<" "<<d[x].a[6]<<" "<<d[x].a[7]<<" "<<d[x].a[8]<<endl;
        return ;
    }
    ll m1=(l+r)/2;
    BT(x*2+1,l,m1);
    BT(x*2+2,m1+1,r);
    d[x]=S(d[x*2+1],d[x*2+2]);
   // cout<<x<<" "<<l<<" "<<r<<" "<<d[x].a[1]+d[x].a[2]+d[x].a[3]+d[x].a[4]+d[x].a[5]+d[x].a[6]+d[x].a[7]+d[x].a[8]<<endl;
   // cout<<d[x].a[1]<<" "<<d[x].a[2]<<" "<<d[x].a[3]<<" "<<d[x].a[4]<<" "<<d[x].a[5]<<" "<<d[x].a[6]<<" "<<d[x].a[7]<<" "<<d[x].a[8]<<endl;

    return ;
}

D R(ll x,ll l,ll r,ll tl,ll tr){
    if(tl<=l && r<=tr)return d[x];
    ll m1=(l+r)/2;
    if(tr<=m1)return R(x*2+1,l,m1,tl,tr);
    if(m1<tl)return R(x*2+2,m1+1,r,tl,tr);
    D x1=R(x*2+1,l,m1,tl,tr);
    D x2=R(x*2+2,m1+1,r,tl,tr);
    return S(x1,x2);
}

void A(ll x,ll l,ll r,ll tl,ll y){
    if(tl<l || r<tl)return ;
    if(l==r){
        a[l]=y;
        d[x].a[1]=0;
        if(a[l]==3)d[x].a[2]=1;
        else d[x].a[2]=0;
        if(a[l]==1)d[x].a[3]=1;
        else d[x].a[3]=0;
        if(a[l]!=1 && a[l]!=3)d[x].a[4]=1;
        else d[x].a[4]=0;
        d[x].a[5]=0;
        if(a[l]>3)d[x].a[6]=1;
        else d[x].a[6]=0;
        if(a[l]>1)d[x].a[7]=1;
        else d[x].a[7]=0;
        if(a[l]>3)d[x].a[8]=a[l]-2;
        else if(a[l]>1)d[x].a[8]=a[l]-1;
        else d[x].a[8]=a[l];
        d[x].a[9]=0;
        d[x].a[10]=1;
        d[x].a[11]=1;
        d[x].a[12]=8;
        return ;
    }
    ll m1=(l+r)/2;
    A(x*2+1,l,m1,tl,y);
    A(x*2+2,m1+1,r,tl,y);
    d[x]=S(d[x*2+1],d[x*2+2]);
    return;
}

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=ll(c-'0');
    }
    BT(0,1,n);
    cout<<(d[0].a[1]+d[0].a[2]+d[0].a[3]+d[0].a[4]+d[0].a[5]+d[0].a[6]+d[0].a[7]+d[0].a[8])%MOD<<endl;
    for(int i=1;i<=m;i++){
        ll l,r,tp;
        cin>>tp>>l>>r;
        if(tp==1){
            D res=R(0,1,n,l,r);
            cout<<(res.a[1]+res.a[2]+res.a[3]+res.a[4]+res.a[5]+res.a[6]+res.a[7]+res.a[8])%MOD<<endl;
        }else{
            A(0,1,n,l,r);
        }
    }


    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2104 KB Output is correct
2 Correct 36 ms 3764 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2104 KB Output is correct
2 Correct 36 ms 3764 KB Output is correct
3 Correct 67 ms 27656 KB Output is correct
4 Correct 66 ms 27592 KB Output is correct
5 Correct 65 ms 27648 KB Output is correct
6 Correct 73 ms 27772 KB Output is correct
7 Correct 84 ms 27876 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 31 ms 2104 KB Output is correct
8 Correct 36 ms 3764 KB Output is correct
9 Correct 24 ms 2100 KB Output is correct
10 Correct 37 ms 3848 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 31 ms 2104 KB Output is correct
8 Correct 36 ms 3764 KB Output is correct
9 Correct 67 ms 27656 KB Output is correct
10 Correct 66 ms 27592 KB Output is correct
11 Correct 65 ms 27648 KB Output is correct
12 Correct 73 ms 27772 KB Output is correct
13 Correct 84 ms 27876 KB Output is correct
14 Correct 24 ms 2100 KB Output is correct
15 Correct 37 ms 3848 KB Output is correct
16 Correct 61 ms 27792 KB Output is correct
17 Correct 53 ms 27788 KB Output is correct
18 Correct 62 ms 27888 KB Output is correct
19 Correct 76 ms 27980 KB Output is correct
20 Correct 69 ms 27980 KB Output is correct