oj.uz

Submission #443782

# Submission time Handle Problem Language Result Execution time Memory
443782 2021-07-12T05:37:15 Z JovanB Lucky Numbers (RMI19_lucky) C++17
100 / 100
 171 ms 128836 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);
}

void query(int node, int l, int r, int tl, int tr){
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        nodes.push_back(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);
    int 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;
            clr(dm);
            query(1, 1, n, l, r);
            cpy(dm, nodes[0]);
            assert(nodes.size() <= 60);
            for(int i=1; i<nodes.size(); i++){
                mrg(dm+i, dm+i-1, nodes[i]);
            }
            int x = dm+nodes.size()-1;
            res = 0;
            for(int i=1; i<=3; i++) for(int j=1; j<=3; j++) res = add(res, add(seg[x][0][i][j], seg[x][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;
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for(int i=1; i<nodes.size(); i++){
      |                          ~^~~~~~~~~~~~~

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 1 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 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 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 8420 KB Output is correct
2 Correct 61 ms 15748 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8420 KB Output is correct
2 Correct 61 ms 15748 KB Output is correct
3 Correct 137 ms 122664 KB Output is correct
4 Correct 141 ms 122628 KB Output is correct
5 Correct 156 ms 128836 KB Output is correct
6 Correct 166 ms 128828 KB Output is correct
7 Correct 162 ms 128792 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 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 44 ms 8420 KB Output is correct
8 Correct 61 ms 15748 KB Output is correct
9 Correct 46 ms 8372 KB Output is correct
10 Correct 65 ms 15748 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 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 44 ms 8420 KB Output is correct
8 Correct 61 ms 15748 KB Output is correct
9 Correct 137 ms 122664 KB Output is correct
10 Correct 141 ms 122628 KB Output is correct
11 Correct 156 ms 128836 KB Output is correct
12 Correct 166 ms 128828 KB Output is correct
13 Correct 162 ms 128792 KB Output is correct
14 Correct 46 ms 8372 KB Output is correct
15 Correct 65 ms 15748 KB Output is correct
16 Correct 141 ms 122644 KB Output is correct
17 Correct 153 ms 122576 KB Output is correct
18 Correct 151 ms 128776 KB Output is correct
19 Correct 171 ms 128832 KB Output is correct
20 Correct 168 ms 128720 KB Output is correct