oj.uz

Submission #711480

# Submission time Handle Problem Language Result Execution time Memory
711480 2023-03-17T04:58:48 Z Nursik Lucky Numbers (RMI19_lucky) C++17
100 / 100
 124 ms 38436 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 1e5 + 1, maxm = 1e4 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, block = 5000, p2 = 31, bit = 30;
const ld eps = 1e-9;

int n, q;
string s;
struct node{
    ll s[2][2];
    ll e[2][2];
    ll b[2][2];
    node(){
        for (int i = 0; i < 2; ++i){
            for (int j = 0; j < 2; ++j){
                s[i][j] = 0;
                e[i][j] = 0;
                b[i][j] = 0;
            }
        }
    }
} t[maxn * 4];
node merge(node lx, node rx){
    node cur;
    for (int i = 0; i < 2; ++i){
        for (int j = 0; j < 2; ++j){
            cur.s[i][j] = 0;
            cur.e[i][j] = 0;
            cur.b[i][j] = 0;
        }
    }
    for (int i = 0; i < 2; ++i){
        for (int j = 0; j < 2; ++j){
            for (int jj = 0; jj < 2; ++jj){
                for (int k = 0; k < 2; ++k){
                    if (!(j == 1 && jj == 1)){
                        cur.s[i][k] = (cur.s[i][k] + lx.s[i][j] * rx.s[jj][k] % mod) % mod;
                        cur.s[i][k] = (cur.s[i][k] + lx.s[i][j] * rx.e[jj][k] % mod) % mod;
                        cur.s[i][k] = (cur.s[i][k] + lx.s[i][j] * rx.b[jj][k] % mod) % mod;
                        cur.s[i][k] = (cur.s[i][k] + lx.e[i][j] * rx.s[jj][k] % mod) % mod;
                        
                        cur.e[i][k] = (cur.e[i][k] + lx.e[i][j] * rx.e[jj][k] % mod) % mod;

                        cur.b[i][k] = (cur.b[i][k] + lx.e[i][j] * rx.b[jj][k] % mod) % mod;
                        cur.b[i][k] = (cur.b[i][k] + lx.b[i][j] * rx.e[jj][k] % mod) % mod;
                        cur.b[i][k] = (cur.b[i][k] + lx.b[i][j] * rx.s[jj][k] % mod) % mod;
                        cur.b[i][k] = (cur.b[i][k] + lx.b[i][j] * rx.b[jj][k] % mod ) % mod;
                    }
                }
            }
        }
    }
    return cur;
}
void build(int v = 1, int tl = 1, int tr = n){
    if (tl == tr){
        for (int i = 0; i < 2; ++i){
            for (int j = 0; j < 2; ++j){
                t[v].s[i][j] = 0;
                t[v].e[i][j] = 0;
                t[v].b[i][j] = 0;
            }
        }
        int val = s[tl] - '0';
        for (int i = 0; i <= 9; ++i){
            if (i < val){
                if (i == 1){
                    t[v].s[0][1] += 1;
                }
                else if (i == 3){
                    t[v].s[1][0] += 1;
                }
                else{
                    t[v].s[0][0] += 1;
                }
            }
            else if (i == val){
                if (i == 1){
                    t[v].e[0][1] += 1;
                }
                else if (i == 3){
                    t[v].e[1][0] += 1;
                }
                else{
                    t[v].e[0][0] += 1;
                }
            }
            else{
                if (i == 1){
                    t[v].b[0][1] += 1;
                }
                else if (i == 3){
                    t[v].b[1][0] += 1;
                }
                else{
                    t[v].b[0][0] += 1;
                }
            }
        }
        return;
    }
    int tm = (tl + tr) / 2;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
    /*cout << v << '\n';
    cout << tl << " " << tr << '\n';
    cout << t[v].s[0][0] << " " << t[v].s[0][1] << " " << t[v].s[1][0] << " " << t[v].s[1][1] << '\n';
    cout << t[v].e[0][0] << " " << t[v].e[0][1] << " " << t[v].e[1][0] << " " << t[v].e[1][1] << '\n';
    cout << t[v].b[0][0] << " " << t[v].b[0][1] << " " << t[v].b[1][0] << " " << t[v].b[1][1] << '\n';*/
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
    if (tl == tr){
        for (int i = 0; i < 2; ++i){
            for (int j = 0; j < 2; ++j){
                t[v].s[i][j] = 0;
                t[v].e[i][j] = 0;
                t[v].b[i][j] = 0;
            }
        }
        for (int i = 0; i <= 9; ++i){
            if (i < val){
                if (i == 1){
                    t[v].s[0][1] += 1;
                }
                else if (i == 3){
                    t[v].s[1][0] += 1;
                }
                else{
                    t[v].s[0][0] += 1;
                }
            }
            else if (i == val){
                if (i == 1){
                    t[v].e[0][1] += 1;
                }
                else if (i == 3){
                    t[v].e[1][0] += 1;
                }
                else{
                    t[v].e[0][0] += 1;
                }
            }
            else{
                if (i == 1){
                    t[v].b[0][1] += 1;
                }
                else if (i == 3){
                    t[v].b[1][0] += 1;
                }
                else{
                    t[v].b[0][0] += 1;
                }
            }
        }
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm){
        upd(pos, val, v + v, tl, tm);
    }
    else{
        upd(pos, val, v + v + 1, tm + 1, tr);
    }
    t[v] = merge(t[v + v], t[v + v + 1]);
}
node get(int l, int r, int v = 1, int tl = 1, int tr = n){
    if (l <= tl && tr <= r){
        return t[v];
    }
    int tm = (tl + tr) / 2;
    if (r <= tm){
        return get(l, r, v + v, tl, tm);
    }
    if (l > tm){
        return get(l, r, v + v + 1, tm + 1, tr);
    }
    return merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    cin >> n >> q;
    cin >> s;
    s = '#' + s;
    build();
    ll answ = 0;
    for (int i = 0; i < 2; ++i){
        for (int j = 0; j < 2; ++j){
            answ = (answ + t[1].s[i][j] + t[1].e[i][j]) % mod;
        }
    }
    cout << answ << '\n';
   // exit(0);
    for (int type, l, r, pos, dig, i = 1; i <= q; ++i){
        cin >> type;
        if (type == 1){
            cin >> l >> r;
            node ans = get(l, r);
            answ = 0;
            for (int j = 0; j < 2; ++j){
                for (int k = 0; k < 2; ++k){
                    answ = (answ + ans.s[j][k] + ans.e[j][k]) % mod;
                }
            }
            cout << answ << '\n';
        }
        else{
            cin >> pos >> dig;
            upd(pos, dig);
        }
    }
}
/*
ajj, ajj, ajj, ajj, aj, aj, aj, aj, aj, aj, ak, ak, ak, ak, ak, ai, ai, ai
 */

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 16 ms 37792 KB Output is correct
3 Correct 17 ms 37784 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 16 ms 37792 KB Output is correct
3 Correct 17 ms 37784 KB Output is correct
4 Correct 18 ms 37792 KB Output is correct
5 Correct 16 ms 37852 KB Output is correct
6 Correct 16 ms 37808 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 37956 KB Output is correct
2 Correct 60 ms 38056 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 37956 KB Output is correct
2 Correct 60 ms 38056 KB Output is correct
3 Correct 90 ms 38344 KB Output is correct
4 Correct 105 ms 38328 KB Output is correct
5 Correct 111 ms 38380 KB Output is correct
6 Correct 116 ms 38420 KB Output is correct
7 Correct 107 ms 38324 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 16 ms 37792 KB Output is correct
3 Correct 17 ms 37784 KB Output is correct
4 Correct 18 ms 37792 KB Output is correct
5 Correct 16 ms 37852 KB Output is correct
6 Correct 16 ms 37808 KB Output is correct
7 Correct 48 ms 37956 KB Output is correct
8 Correct 60 ms 38056 KB Output is correct
9 Correct 55 ms 38092 KB Output is correct
10 Correct 64 ms 38060 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 16 ms 37792 KB Output is correct
3 Correct 17 ms 37784 KB Output is correct
4 Correct 18 ms 37792 KB Output is correct
5 Correct 16 ms 37852 KB Output is correct
6 Correct 16 ms 37808 KB Output is correct
7 Correct 48 ms 37956 KB Output is correct
8 Correct 60 ms 38056 KB Output is correct
9 Correct 90 ms 38344 KB Output is correct
10 Correct 105 ms 38328 KB Output is correct
11 Correct 111 ms 38380 KB Output is correct
12 Correct 116 ms 38420 KB Output is correct
13 Correct 107 ms 38324 KB Output is correct
14 Correct 55 ms 38092 KB Output is correct
15 Correct 64 ms 38060 KB Output is correct
16 Correct 92 ms 38248 KB Output is correct
17 Correct 92 ms 38260 KB Output is correct
18 Correct 120 ms 38436 KB Output is correct
19 Correct 123 ms 38304 KB Output is correct
20 Correct 124 ms 38344 KB Output is correct