oj.uz

Submission #493887

# Submission time Handle Problem Language Result Execution time Memory
493887 2021-12-13T09:54:52 Z leaked Lucky Numbers (RMI19_lucky) C++17
73 / 100
 200 ms 43108 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;
    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 42572 KB Output is correct
2 Correct 20 ms 42568 KB Output is correct
3 Correct 22 ms 42492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42572 KB Output is correct
2 Correct 20 ms 42568 KB Output is correct
3 Correct 22 ms 42492 KB Output is correct
4 Correct 21 ms 42484 KB Output is correct
5 Correct 25 ms 42560 KB Output is correct
6 Correct 24 ms 42572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 42720 KB Output is correct
2 Correct 103 ms 42680 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 42720 KB Output is correct
2 Correct 103 ms 42680 KB Output is correct
3 Correct 168 ms 42920 KB Output is correct
4 Correct 164 ms 42920 KB Output is correct
5 Correct 174 ms 42948 KB Output is correct
6 Correct 188 ms 42996 KB Output is correct
7 Correct 190 ms 42956 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42572 KB Output is correct
2 Correct 20 ms 42568 KB Output is correct
3 Correct 22 ms 42492 KB Output is correct
4 Correct 21 ms 42484 KB Output is correct
5 Correct 25 ms 42560 KB Output is correct
6 Correct 24 ms 42572 KB Output is correct
7 Correct 83 ms 42720 KB Output is correct
8 Correct 103 ms 42680 KB Output is correct
9 Correct 88 ms 42600 KB Output is correct
10 Correct 108 ms 42624 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42572 KB Output is correct
2 Correct 20 ms 42568 KB Output is correct
3 Correct 22 ms 42492 KB Output is correct
4 Correct 21 ms 42484 KB Output is correct
5 Correct 25 ms 42560 KB Output is correct
6 Correct 24 ms 42572 KB Output is correct
7 Correct 83 ms 42720 KB Output is correct
8 Correct 103 ms 42680 KB Output is correct
9 Correct 168 ms 42920 KB Output is correct
10 Correct 164 ms 42920 KB Output is correct
11 Correct 174 ms 42948 KB Output is correct
12 Correct 188 ms 42996 KB Output is correct
13 Correct 190 ms 42956 KB Output is correct
14 Correct 88 ms 42600 KB Output is correct
15 Correct 108 ms 42624 KB Output is correct
16 Correct 159 ms 43052 KB Output is correct
17 Correct 162 ms 43108 KB Output is correct
18 Correct 189 ms 43028 KB Output is correct
19 Execution timed out 216 ms 43008 KB Time limit exceeded
20 Halted 0 ms 0 KB -