oj.uz

Submission #493864

# Submission time Handle Problem Language Result Execution time Memory
493864 2021-12-13T08:52:22 Z leaked Lucky Numbers (RMI19_lucky) C++14
28 / 100
 200 ms 42724 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;
}
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 s=0;s<=2;s++){
            for(int d1=0;d1<=2;d1++){
                for(int d2=0;d2<=2;d2++){
                    /// need to count d3,d4
                    int nf=(f==1?s:f);
                    int sm=0;
                    for(int j=0;j<=2;j++)
                        add(sm,b.dp[j][d2][s]);
                    for(int j=0;j<=2;j++){
                        if(j==0){
                            int w=sm;
                            add(w,-b.dp[1][d2][s]);
                            add(c.dp[d1][d2][nf],mult(a.dp[d1][j][f],w));
                        }
                        else{
                            add(c.dp[d1][d2][nf],mult(a.dp[d1][j][f],sm));
                        }
                    }
                }
            }
        }
    }
    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;
    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 20 ms 42552 KB Output is correct
2 Correct 20 ms 42532 KB Output is correct
3 Correct 20 ms 42480 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42552 KB Output is correct
2 Correct 20 ms 42532 KB Output is correct
3 Correct 20 ms 42480 KB Output is correct
4 Correct 28 ms 42568 KB Output is correct
5 Correct 19 ms 42572 KB Output is correct
6 Correct 23 ms 42480 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 207 ms 42724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 207 ms 42724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42552 KB Output is correct
2 Correct 20 ms 42532 KB Output is correct
3 Correct 20 ms 42480 KB Output is correct
4 Correct 28 ms 42568 KB Output is correct
5 Correct 19 ms 42572 KB Output is correct
6 Correct 23 ms 42480 KB Output is correct
7 Execution timed out 207 ms 42724 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42552 KB Output is correct
2 Correct 20 ms 42532 KB Output is correct
3 Correct 20 ms 42480 KB Output is correct
4 Correct 28 ms 42568 KB Output is correct
5 Correct 19 ms 42572 KB Output is correct
6 Correct 23 ms 42480 KB Output is correct
7 Execution timed out 207 ms 42724 KB Time limit exceeded
8 Halted 0 ms 0 KB -