oj.uz

Submission #730190

# Submission time Handle Problem Language Result Execution time Memory
730190 2023-04-25T11:52:25 Z DJeniUp Lucky Numbers (RMI19_lucky) C++17
64 / 100
 200 ms 28048 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);
}

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;
        cin>>l>>l>>r;
        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;
    }


    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2096 KB Output is correct
2 Correct 35 ms 3924 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2096 KB Output is correct
2 Correct 35 ms 3924 KB Output is correct
3 Correct 53 ms 27852 KB Output is correct
4 Correct 54 ms 27876 KB Output is correct
5 Correct 59 ms 27900 KB Output is correct
6 Correct 64 ms 28000 KB Output is correct
7 Correct 64 ms 28048 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 28 ms 2096 KB Output is correct
8 Correct 35 ms 3924 KB Output is correct
9 Execution timed out 1071 ms 2004 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 28 ms 2096 KB Output is correct
8 Correct 35 ms 3924 KB Output is correct
9 Correct 53 ms 27852 KB Output is correct
10 Correct 54 ms 27876 KB Output is correct
11 Correct 59 ms 27900 KB Output is correct
12 Correct 64 ms 28000 KB Output is correct
13 Correct 64 ms 28048 KB Output is correct
14 Execution timed out 1071 ms 2004 KB Time limit exceeded
15 Halted 0 ms 0 KB -