oj.uz

Submission #443788

# Submission time Handle Problem Language Result Execution time Memory
443788 2021-07-12T05:47:57 Z JovanB Lucky Numbers (RMI19_lucky) C++17
100 / 100
 62 ms 12896 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][3][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[3][2], R[3][2];

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 1 ms 204 KB Output is correct
2 Correct 1 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 1 ms 204 KB Output is correct
2 Correct 1 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 20 ms 1168 KB Output is correct
2 Correct 26 ms 1968 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1168 KB Output is correct
2 Correct 26 ms 1968 KB Output is correct
3 Correct 46 ms 12860 KB Output is correct
4 Correct 46 ms 12800 KB Output is correct
5 Correct 52 ms 12896 KB Output is correct
6 Correct 61 ms 12872 KB Output is correct
7 Correct 59 ms 12856 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 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 20 ms 1168 KB Output is correct
8 Correct 26 ms 1968 KB Output is correct
9 Correct 20 ms 1140 KB Output is correct
10 Correct 26 ms 1868 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 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 20 ms 1168 KB Output is correct
8 Correct 26 ms 1968 KB Output is correct
9 Correct 46 ms 12860 KB Output is correct
10 Correct 46 ms 12800 KB Output is correct
11 Correct 52 ms 12896 KB Output is correct
12 Correct 61 ms 12872 KB Output is correct
13 Correct 59 ms 12856 KB Output is correct
14 Correct 20 ms 1140 KB Output is correct
15 Correct 26 ms 1868 KB Output is correct
16 Correct 46 ms 12860 KB Output is correct
17 Correct 45 ms 12772 KB Output is correct
18 Correct 51 ms 12852 KB Output is correct
19 Correct 56 ms 12868 KB Output is correct
20 Correct 62 ms 12848 KB Output is correct