oj.uz

Submission #443787

# Submission time Handle Problem Language Result Execution time Memory
443787 2021-07-12T05:46:28 Z JovanB Lucky Numbers (RMI19_lucky) C++17
100 / 100
 63 ms 21184 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][2][2];

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

void cpy(int node, int pnode){
    for(int i=0; i<=2; i++) for(int j=0; j<=1; j++) for(int k=0; k<=1; 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=0; i<=1; i++){
        for(int p=0; p<=2; p++) L[p][i] = 0;
        for(int f=0; f<=1; f++){
            for(int p=0; p<=2; p++) L[p][i] = add(L[p][i], seg[a][p][i][f]);
        }
    }
    for(int i=0; i<=1; i++){
        for(int p=0; p<=2; p++) R[p][i] = 0;
        for(int f=0; f<=1; f++){
            for(int p=0; p<=2; p++) R[p][i] = add(R[p][i], seg[b][p][f][i]);
        }
    }
    for(int i=0; i<=1; i++){
        for(int j=0; j<=1; 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=1; g<=1; 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][0][1]++;
            else if(i == 3) seg[node][c][1][0]++;
            else seg[node][c][0][0]++;
        }
        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][0][1]++;
            else if(i == 3) seg[node][c][1][0]++;
            else seg[node][c][0][0]++;
        }
        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=0; i<=1; i++) for(int j=0; j<=1; 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=0; i<=1; i++) for(int j=0; j<=1; 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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1612 KB Output is correct
2 Correct 30 ms 2996 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1612 KB Output is correct
2 Correct 30 ms 2996 KB Output is correct
3 Correct 54 ms 21068 KB Output is correct
4 Correct 52 ms 21068 KB Output is correct
5 Correct 62 ms 21184 KB Output is correct
6 Correct 63 ms 21060 KB Output is correct
7 Correct 63 ms 21088 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 21 ms 1612 KB Output is correct
8 Correct 30 ms 2996 KB Output is correct
9 Correct 22 ms 1644 KB Output is correct
10 Correct 30 ms 2940 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 21 ms 1612 KB Output is correct
8 Correct 30 ms 2996 KB Output is correct
9 Correct 54 ms 21068 KB Output is correct
10 Correct 52 ms 21068 KB Output is correct
11 Correct 62 ms 21184 KB Output is correct
12 Correct 63 ms 21060 KB Output is correct
13 Correct 63 ms 21088 KB Output is correct
14 Correct 22 ms 1644 KB Output is correct
15 Correct 30 ms 2940 KB Output is correct
16 Correct 52 ms 21024 KB Output is correct
17 Correct 50 ms 20944 KB Output is correct
18 Correct 58 ms 21060 KB Output is correct
19 Correct 61 ms 21056 KB Output is correct
20 Correct 63 ms 21060 KB Output is correct