oj.uz

Submission #493865

# Submission time Handle Problem Language Result Execution time Memory
493865 2021-12-13T09:01:57 Z leaked Lucky Numbers (RMI19_lucky) C++14
46 / 100
 200 ms 43328 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e5+1;
const int M=1e9+7;
void add(int &a,int b){
    a+=b;
    if(a>=M)
        a-=M;
    else if(a<0)
        a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int sm1[3][3];
int sm2[3][3];
struct node{
    int dp[3][3][3];
    node(){
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++)
                dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;
        }
    }
    void clr(){
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++)
                dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;
        }
    }
};
node mg(const node &a,const node &b){
    node c;
    for(int f=0;f<=2;f++){
        for(int d=0;d<=2;d++){
            sm1[d][f]=sm2[d][f]=0;
            for(int j=0;j<=2;j++)
                add(sm1[d][f],a.dp[d][j][f]),add(sm2[d][f],b.dp[j][d][f]);
        }
    }
    for(int f=0;f<=2;f++){
        for(int s=0;s<=2;s++){
            for(int d1=0;d1<=2;d1++){
                for(int d2=0;d2<=2;d2++){
                    int nf=(f!=1?f:s);
                    add(c.dp[d1][d2][nf],mult(sm1[d1][f],sm2[d2][s]));
                    add(c.dp[d1][d2][nf],-mult(a.dp[d1][0][f],b.dp[1][d2][s]));
                }
            }
        }
    }
    return c;
}

int gd(int x){
    if(x==1)
        return 0;
    if(x==3)
        return 1;
    return 2;
}
node t[4*N];
int a[N];
void build(int v,int tl,int tr){
    if(tl==tr){
        for(int j=0;j<=9;j++){
            int f=(j>a[tl]?2:a[tl]==j);
            add(t[v].dp[gd(j)][gd(j)][f],1);
        }
    }
    else{
        int tm=(tl+tr)>>1;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=mg(t[2*v],t[2*v+1]);
    }
}
void upd(int i,int x,int v,int tl,int tr){
    if(tl==tr){
        t[v].clr();
        a[i]=x;
        for(int j=0;j<=9;j++){
            int f=(j>a[tl]?2:a[tl]==j);
            add(t[v].dp[gd(j)][gd(j)][f],1);
        }
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=i)
        upd(i,x,2*v,tl,tm);
    else
        upd(i,x,2*v+1,tm+1,tr);
    t[v]=mg(t[2*v],t[2*v+1]);
}
node ans;
bool is=0;
void get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
        if(is)
            ans=mg(ans,t[v]);
        else
            ans=t[v];
        is=1;
        return;
    }
    if(tl>r||tr<l)
        return;
    int tm=(tl+tr)>>1;
    get(l,r,2*v,tl,tm);
    get(l,r,2*v+1,tm+1,tr);
    return;
}
int eval(){
    int me=0;
    for(int f=0;f<=1;f++){
        for(int x=0;x<=2;x++)
            for(int y=0;y<=2;y++)
                add(me,ans.dp[x][y][f]);
    }
    return me;
}
signed main(){
    fast_rmi;
    int n,q;
//    n=100'000,q=0;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
    }
    build(1,0,n-1);
    ans=t[1];
    cout<<eval()<<'\n';
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            is=0;
            int l,r;
            cin>>l>>r;--l;--r;
            get(l,r,1,0,n-1);
            cout<<eval()<<'\n';
        }
        else{
            int i,x;
            cin>>i>>x;
            upd(i-1,x,1,0,n-1);
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42572 KB Output is correct
2 Correct 19 ms 42556 KB Output is correct
3 Correct 22 ms 42452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42572 KB Output is correct
2 Correct 19 ms 42556 KB Output is correct
3 Correct 22 ms 42452 KB Output is correct
4 Correct 20 ms 42692 KB Output is correct
5 Correct 19 ms 42572 KB Output is correct
6 Correct 20 ms 42528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 42564 KB Output is correct
2 Correct 104 ms 42772 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 42564 KB Output is correct
2 Correct 104 ms 42772 KB Output is correct
3 Correct 183 ms 43140 KB Output is correct
4 Correct 154 ms 43328 KB Output is correct
5 Correct 177 ms 43128 KB Output is correct
6 Execution timed out 207 ms 43192 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42572 KB Output is correct
2 Correct 19 ms 42556 KB Output is correct
3 Correct 22 ms 42452 KB Output is correct
4 Correct 20 ms 42692 KB Output is correct
5 Correct 19 ms 42572 KB Output is correct
6 Correct 20 ms 42528 KB Output is correct
7 Correct 88 ms 42564 KB Output is correct
8 Correct 104 ms 42772 KB Output is correct
9 Correct 96 ms 42840 KB Output is correct
10 Correct 116 ms 42760 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42572 KB Output is correct
2 Correct 19 ms 42556 KB Output is correct
3 Correct 22 ms 42452 KB Output is correct
4 Correct 20 ms 42692 KB Output is correct
5 Correct 19 ms 42572 KB Output is correct
6 Correct 20 ms 42528 KB Output is correct
7 Correct 88 ms 42564 KB Output is correct
8 Correct 104 ms 42772 KB Output is correct
9 Correct 183 ms 43140 KB Output is correct
10 Correct 154 ms 43328 KB Output is correct
11 Correct 177 ms 43128 KB Output is correct
12 Execution timed out 207 ms 43192 KB Time limit exceeded
13 Halted 0 ms 0 KB -