oj.uz

Submission #643529

# Submission time Handle Problem Language Result Execution time Memory
643529 2022-09-22T09:54:32 Z boris_mihov Lucky Numbers (RMI19_lucky) C++17
100 / 100
 85 ms 38348 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD  = 1e9 + 7;
const int INF  = 1e9;

struct Node2
{
    __int128 smaller[2][2];
    __int128 equal[2][2];
    __int128 bigger[2][2];
    Node2()
    {
        smaller[0][0] = smaller[0][1] = smaller[1][0] = smaller[1][1] = 0;
        equal[0][0] = equal[0][1] = equal[1][0] = equal[1][1] = 0;
        bigger[0][0] = bigger[0][1] = bigger[1][0] = bigger[1][1] = 0;
    }
};

struct Node
{
    llong smaller[2][2];
    llong equal[2][2];
    llong bigger[2][2];
    Node()
    {
        smaller[0][0] = smaller[0][1] = smaller[1][0] = smaller[1][1] = 0;
        equal[0][0] = equal[0][1] = equal[1][0] = equal[1][1] = 0;
        bigger[0][0] = bigger[0][1] = bigger[1][0] = bigger[1][1] = 0;
    }

    Node(int digit)
    {
        smaller[0][0] = digit - (digit > 3) - (digit > 1);
        smaller[0][1] = (digit > 1);
        smaller[1][0] = (digit > 3);
        equal[0][0] = (digit != 1) && (digit != 3);
        equal[0][1] = (digit == 1);
        equal[1][0] = (digit == 3);
        bigger[0][0] = 9 - digit - (digit < 3) - (digit < 1);
        bigger[0][1] = (digit < 1);
        bigger[1][0] = (digit < 3);
        smaller[1][1] = 0;
        equal[1][1] = 0;
        bigger[1][1] = 0;
    }

    inline void print()
    {
        llong ans = 0;
        ans += smaller[0][0];
        ans += smaller[0][1];
        ans += smaller[1][0];
        ans += smaller[1][1];
        ans += equal[0][0];
        ans += equal[0][1];
        ans += equal[1][0];
        ans += equal[1][1]; ans %= MOD;
        std::cout << ans << '\n';
    }

    inline void print2()
    {
        llong ans = 0;
        std::cout << smaller[0][0] << '\n';
        std::cout << smaller[0][1] << '\n';
        std::cout << smaller[1][0] << '\n';
        std::cout << smaller[1][1] << '\n';
        std::cout << equal[0][0] << '\n';
        std::cout << equal[0][1] << '\n';
        std::cout << equal[1][0] << '\n';
        std::cout << equal[1][1] << '\n';
        std::cout << "\n";
    }
} tree[4*MAXN];

Node combine(Node left, Node right)
{
    if (left.smaller[0][0] == -1) return right;
    if (right.smaller[0][0] == -1) return left;
    Node2 result;
    Node realResult;
    for (int first3 = 0 ; first3 <= 1 ; ++first3)
    {
        for (int last1 = 0 ; last1 <= 1 ; ++last1)
        {
            result.smaller[first3][last1] += left.smaller[first3][0] * right.smaller[0][last1];
            result.smaller[first3][last1] += left.smaller[first3][0] * right.smaller[1][last1];
            result.smaller[first3][last1] += left.smaller[first3][1] * right.smaller[0][last1];
            result.smaller[first3][last1] += left.smaller[first3][0] * right.equal[0][last1];
            result.smaller[first3][last1] += left.smaller[first3][0] * right.equal[1][last1];
            result.smaller[first3][last1] += left.smaller[first3][1] * right.equal[0][last1];
            result.smaller[first3][last1] += left.smaller[first3][0] * right.bigger[0][last1];
            result.smaller[first3][last1] += left.smaller[first3][0] * right.bigger[1][last1];
            result.smaller[first3][last1] += left.smaller[first3][1] * right.bigger[0][last1];
            result.smaller[first3][last1] += left.equal[first3][0] * right.smaller[0][last1];
            result.smaller[first3][last1] += left.equal[first3][0] * right.smaller[1][last1];
            result.smaller[first3][last1] += left.equal[first3][1] * right.smaller[0][last1];
            result.equal[first3][last1] += left.equal[first3][0] * right.equal[0][last1];
            result.equal[first3][last1] += left.equal[first3][0] * right.equal[1][last1];
            result.equal[first3][last1] += left.equal[first3][1] * right.equal[0][last1];
            result.bigger[first3][last1] += left.equal[first3][0] * right.bigger[0][last1];
            result.bigger[first3][last1] += left.equal[first3][0] * right.bigger[1][last1];
            result.bigger[first3][last1] += left.equal[first3][1] * right.bigger[0][last1];
            result.bigger[first3][last1] += left.bigger[first3][0] * right.smaller[0][last1];
            result.bigger[first3][last1] += left.bigger[first3][0] * right.smaller[1][last1];
            result.bigger[first3][last1] += left.bigger[first3][1] * right.smaller[0][last1];
            result.bigger[first3][last1] += left.bigger[first3][0] * right.equal[0][last1];
            result.bigger[first3][last1] += left.bigger[first3][0] * right.equal[1][last1];
            result.bigger[first3][last1] += left.bigger[first3][1] * right.equal[0][last1];
            result.bigger[first3][last1] += left.bigger[first3][0] * right.bigger[0][last1];
            result.bigger[first3][last1] += left.bigger[first3][0] * right.bigger[1][last1];
            result.bigger[first3][last1] += left.bigger[first3][1] * right.bigger[0][last1];
            realResult.smaller[first3][last1] = result.smaller[first3][last1] %= MOD;
            realResult.equal[first3][last1] = result.equal[first3][last1] %= MOD;
            realResult.bigger[first3][last1] = result.bigger[first3][last1] %= MOD;
        }
    }

    return realResult;
}

char s[MAXN];
void build(int l, int r, int node)
{
    if (l == r)
    {
        tree[node] = Node(s[l] - '0');
        return;
    }

    int mid = (l + r) / 2;
    build(l, mid, 2*node);
    build(mid + 1, r, 2*node + 1);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

void update(int l, int r, int node, int queryPos, int queryVal)
{
    if (l == r)
    {
        tree[node] = Node(queryVal);
        return;
    }

    int mid = (l + r) / 2;
    if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
    else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

Node query(int l, int r, int node, int queryL, int queryR)
{
    if (queryL <= l && r <= queryR)
    {
        return tree[node];
    }

    int mid = (l + r) / 2;
    Node result; result.smaller[0][0] = -1;
    if (queryL <= mid) result = combine(result, query(l, mid, 2*node, queryL, queryR));
    if (mid + 1 <= queryR) result = combine(result, query(mid + 1, r, 2*node + 1, queryL, queryR));
    return result;
}

int n, q;
void solve()
{
    build(1, n, 1);
    tree[1].print();
    int x, y; 
    char dig;
    int qType;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> qType >> x;
        if (qType == 1)
        {
            std::cin >> y;
            Node result = query(1, n, 1, x, y);
            result.print();
        }

        if (qType == 2)
        {
            std::cin >> dig;
            update(1, n, 1, x, dig - '0');
        }
    }
}

void read()
{
    std::cin >> n >> q;
    std::cin >> s + 1;
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Compilation message

lucky.cpp: In member function 'void Node::print2()':
lucky.cpp:68:15: warning: unused variable 'ans' [-Wunused-variable]
   68 |         llong ans = 0;
      |               ^~~
lucky.cpp: In function 'void read()':
lucky.cpp:199:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  199 |     std::cin >> s + 1;
      |                 ~~^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 18 ms 37844 KB Output is correct
3 Correct 17 ms 37888 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 18 ms 37844 KB Output is correct
3 Correct 17 ms 37888 KB Output is correct
4 Correct 17 ms 37864 KB Output is correct
5 Correct 16 ms 37844 KB Output is correct
6 Correct 17 ms 37844 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 38064 KB Output is correct
2 Correct 52 ms 38100 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 38064 KB Output is correct
2 Correct 52 ms 38100 KB Output is correct
3 Correct 68 ms 38164 KB Output is correct
4 Correct 76 ms 38164 KB Output is correct
5 Correct 74 ms 38220 KB Output is correct
6 Correct 80 ms 38344 KB Output is correct
7 Correct 82 ms 38348 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 18 ms 37844 KB Output is correct
3 Correct 17 ms 37888 KB Output is correct
4 Correct 17 ms 37864 KB Output is correct
5 Correct 16 ms 37844 KB Output is correct
6 Correct 17 ms 37844 KB Output is correct
7 Correct 41 ms 38064 KB Output is correct
8 Correct 52 ms 38100 KB Output is correct
9 Correct 41 ms 38144 KB Output is correct
10 Correct 48 ms 38036 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 18 ms 37844 KB Output is correct
3 Correct 17 ms 37888 KB Output is correct
4 Correct 17 ms 37864 KB Output is correct
5 Correct 16 ms 37844 KB Output is correct
6 Correct 17 ms 37844 KB Output is correct
7 Correct 41 ms 38064 KB Output is correct
8 Correct 52 ms 38100 KB Output is correct
9 Correct 68 ms 38164 KB Output is correct
10 Correct 76 ms 38164 KB Output is correct
11 Correct 74 ms 38220 KB Output is correct
12 Correct 80 ms 38344 KB Output is correct
13 Correct 82 ms 38348 KB Output is correct
14 Correct 41 ms 38144 KB Output is correct
15 Correct 48 ms 38036 KB Output is correct
16 Correct 70 ms 38168 KB Output is correct
17 Correct 72 ms 38140 KB Output is correct
18 Correct 73 ms 38240 KB Output is correct
19 Correct 85 ms 38148 KB Output is correct
20 Correct 80 ms 38228 KB Output is correct