oj.uz

답안 #443781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443781 2021-07-12T05:36:47 Z JovanB Lucky Numbers (RMI19_lucky) C++17
100 / 100
 198 ms 129104 KB 
#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: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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 8408 KB Output is correct
2 Correct 79 ms 15740 KB Output is correct

Subtask #4
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 8408 KB Output is correct
2 Correct 79 ms 15740 KB Output is correct
3 Correct 161 ms 122656 KB Output is correct
4 Correct 157 ms 122796 KB Output is correct
5 Correct 186 ms 129008 KB Output is correct
6 Correct 198 ms 129104 KB Output is correct
7 Correct 184 ms 129044 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 51 ms 8408 KB Output is correct
8 Correct 79 ms 15740 KB Output is correct
9 Correct 59 ms 8364 KB Output is correct
10 Correct 77 ms 15624 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 51 ms 8408 KB Output is correct
8 Correct 79 ms 15740 KB Output is correct
9 Correct 161 ms 122656 KB Output is correct
10 Correct 157 ms 122796 KB Output is correct
11 Correct 186 ms 129008 KB Output is correct
12 Correct 198 ms 129104 KB Output is correct
13 Correct 184 ms 129044 KB Output is correct
14 Correct 59 ms 8364 KB Output is correct
15 Correct 77 ms 15624 KB Output is correct
16 Correct 158 ms 122820 KB Output is correct
17 Correct 196 ms 122812 KB Output is correct
18 Correct 177 ms 129092 KB Output is correct
19 Correct 195 ms 128992 KB Output is correct
20 Correct 196 ms 129036 KB Output is correct