oj.uz

Submission #443786

# Submission time Handle Problem Language Result Execution time Memory
443786 2021-07-12T05:41:33 Z JovanB Lucky Numbers (RMI19_lucky) C++17
100 / 100
 179 ms 129032 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 1000000007;

int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int mul(int a, int b){ return (1LL*a*b)%MOD; }
int sub(int a, int b){ return add(a, MOD-b); }

int seg[400500][5][5][5];

void clr(int node){
    for(int i=0; i<=2; i++) for(int j=1; j<=3; j++) for(int k=1; k<=3; k++) seg[node][i][j][k] = 0;
}

void cpy(int node, int pnode){
    for(int i=0; i<=2; i++) for(int j=1; j<=3; j++) for(int k=1; k<=3; k++) seg[node][i][j][k] = seg[pnode][i][j][k];
}

int L[5][5], R[5][5];

void mrg(int nnode, int a, int b){
    for(int i=1; i<=3; i++){
        for(int p=0; p<=2; p++) L[p][i] = 0;
        for(int f=1; f<=3; f++){
            for(int p=0; p<=2; p++) L[p][i] = add(L[p][i], seg[a][p][i][f]);
        }
    }
    for(int i=1; i<=3; i++){
        for(int p=0; p<=2; p++) R[p][i] = 0;
        for(int f=1; f<=3; f++){
            for(int p=0; p<=2; p++) R[p][i] = add(R[p][i], seg[b][p][f][i]);
        }
    }
    for(int i=1; i<=3; i++){
        for(int j=1; j<=3; j++){
            seg[nnode][0][i][j] = seg[nnode][1][i][j] = seg[nnode][2][i][j] = 0;
            seg[nnode][0][i][j] = add(seg[nnode][0][i][j], mul(L[0][i], add(R[0][j], add(R[1][j], R[2][j]))));
            seg[nnode][2][i][j] = add(seg[nnode][2][i][j], mul(L[2][i], add(R[0][j], add(R[1][j], R[2][j]))));
            for(int d=0; d<=2; d++) seg[nnode][d][i][j] = add(seg[nnode][d][i][j], mul(L[1][i], R[d][j]));
            for(int k=1; k<=1; k++){
                for(int g=3; g<=3; g++){
                    seg[nnode][0][i][j] = sub(seg[nnode][0][i][j], mul(seg[a][0][i][k], add(seg[b][0][g][j], add(seg[b][1][g][j], seg[b][2][g][j]))));
                    seg[nnode][2][i][j] = sub(seg[nnode][2][i][j], mul(seg[a][2][i][k], add(seg[b][0][g][j], add(seg[b][1][g][j], seg[b][2][g][j]))));
                    for(int d=0; d<=2; d++) seg[nnode][d][i][j] = sub(seg[nnode][d][i][j], mul(seg[a][1][i][k], seg[b][d][g][j]));
                }
            }
        }
    }
}

vector <int> nodes;

string s;

void init(int node, int l, int r){
    if(l == r){
        int d = s[l-1] - '0';
        for(int i=0; i<10; i++){
            int c;
            if(i < d) c = 0;
            else if(i == d) c = 1;
            else c = 2;
            if(i == 1) seg[node][c][1][1]++;
            else if(i == 3) seg[node][c][3][3]++;
            else seg[node][c][2][2]++;
        }
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    mrg(node, node*2, node*2+1);
}

void upd(int node, int l, int r, int x){
    if(l == r){
        clr(node);
        int d = s[l-1] - '0';
        for(int i=0; i<10; i++){
            int c;
            if(i < d) c = 0;
            else if(i == d) c = 1;
            else c = 2;
            if(i == 1) seg[node][c][1][1]++;
            else if(i == 3) seg[node][c][3][3]++;
            else seg[node][c][2][2]++;
        }
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x);
    else upd(node*2+1, mid+1, r, x);
    mrg(node, node*2, node*2+1);
}

int tdm;
int dm;

void query(int node, int l, int r, int tl, int tr){
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        if(tdm == 0){
            tdm = dm;
            cpy(dm, node);
        }
        else{
            tdm++;
            mrg(tdm, tdm-1, node);
        }
        return;
    }
    int mid = (l+r)/2;
    query(node*2, l, mid, tl, tr);
    query(node*2+1, mid+1, r, tl, tr);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, qrs;
    cin >> n >> qrs;
    cin >> s;
    init(1, 1, n);
    dm = 4*n+1;
    cpy(dm, 1);
    int res = 0;
    for(int i=1; i<=3; i++) for(int j=1; j<=3; j++) res = add(res, add(seg[dm][0][i][j], seg[dm][1][i][j]));
    cout << res << "\n";
    while(qrs--){
        int typ;
        cin >> typ;
        if(typ == 1){
            nodes.clear();
            int l, r;
            cin >> l >> r;
            tdm = 0;
            query(1, 1, n, l, r);
            res = 0;
            for(int i=1; i<=3; i++) for(int j=1; j<=3; j++) res = add(res, add(seg[tdm][0][i][j], seg[tdm][1][i][j]));
            cout << res << "\n";
        }
        else{
            int a;
            char b;
            cin >> a >> b;
            s[a-1] = b;
            upd(1, 1, n, a);
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8496 KB Output is correct
2 Correct 56 ms 15748 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8496 KB Output is correct
2 Correct 56 ms 15748 KB Output is correct
3 Correct 137 ms 122796 KB Output is correct
4 Correct 148 ms 122820 KB Output is correct
5 Correct 162 ms 128964 KB Output is correct
6 Correct 179 ms 129032 KB Output is correct
7 Correct 163 ms 128944 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 44 ms 8496 KB Output is correct
8 Correct 56 ms 15748 KB Output is correct
9 Correct 45 ms 8460 KB Output is correct
10 Correct 65 ms 15692 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 44 ms 8496 KB Output is correct
8 Correct 56 ms 15748 KB Output is correct
9 Correct 137 ms 122796 KB Output is correct
10 Correct 148 ms 122820 KB Output is correct
11 Correct 162 ms 128964 KB Output is correct
12 Correct 179 ms 129032 KB Output is correct
13 Correct 163 ms 128944 KB Output is correct
14 Correct 45 ms 8460 KB Output is correct
15 Correct 65 ms 15692 KB Output is correct
16 Correct 158 ms 122724 KB Output is correct
17 Correct 142 ms 122784 KB Output is correct
18 Correct 170 ms 128836 KB Output is correct
19 Correct 169 ms 128952 KB Output is correct
20 Correct 169 ms 128964 KB Output is correct