Submission #643529

#	Time	Username	Problem	Language	Result	Execution time	Memory
643529		boris_mihov	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	85 ms	38348 KiB

lucky

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

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27