Submission #443781

#	Time	Username	Problem	Language	Result	Execution time	Memory
443781		JovanB	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	198 ms	129104 KiB

lucky

#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 (stderr)

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

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27