Submission #331084

#	Time	Username	Problem	Language	Result	Execution time	Memory
331084		evpipis	Lucky Numbers (RMI19_lucky)	C++11	100 / 100	55 ms	13548 KiB

lucky

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7, len = 1e5+5;
int arr[len];
char str[len];
int n, q;

int add(int a, int b){
    return (a+b)%mod;
}

int sub(int a, int b){
    return (mod+a-b)%mod;
}

int mul(int a, int b){
    return (a*1LL*b)%mod;
}

struct node{
    int sm, sm3, sm1, sm31;
    int eq, eq3, eq1, eq31;
    int al, al3, al1, al31;

    node(){}

    node(int d){
        sm = d;
        sm3 = (d > 3);
        sm1 = (d > 1);
        sm31 = 0;

        eq = 1;
        eq3 = (d == 3);
        eq1 = (d == 1);
        eq31 = 0;

        al = 10;
        al3 = 1;
        al1 = 1;
        al31 = 0;
    }

    void print(){
        printf("--- node ---\n");
        printf("sm = %d\neq = %d\nal = %d\n", sm, eq, al);
        printf("------------\n");
    }
} tree[4*len];

node join(node lef, node rig){
    node res;

    res.eq = sub(mul(lef.eq, rig.eq), mul(lef.eq1, rig.eq3));
    res.eq3 = sub(mul(lef.eq3, rig.eq), mul(lef.eq31, rig.eq3));
    res.eq1 = sub(mul(lef.eq, rig.eq1), mul(lef.eq1, rig.eq31));
    res.eq31 = sub(mul(lef.eq3, rig.eq1), mul(lef.eq31, rig.eq31));

    res.al = sub(mul(lef.al, rig.al), mul(lef.al1, rig.al3));
    res.al3 = sub(mul(lef.al3, rig.al), mul(lef.al31, rig.al3));
    res.al1 = sub(mul(lef.al, rig.al1), mul(lef.al1, rig.al31));
    res.al31 = sub(mul(lef.al3, rig.al1), mul(lef.al31, rig.al31));

    res.sm = add(sub(mul(lef.sm, rig.al), mul(lef.sm1, rig.al3)),
                 sub(mul(lef.eq, rig.sm), mul(lef.eq1, rig.sm3)));
    res.sm3 = add(sub(mul(lef.sm3, rig.al), mul(lef.sm31, rig.al3)),
                  sub(mul(lef.eq3, rig.sm), mul(lef.eq31, rig.sm3)));
    res.sm1 = add(sub(mul(lef.sm, rig.al1), mul(lef.sm1, rig.al31)),
                  sub(mul(lef.eq, rig.sm1), mul(lef.eq1, rig.sm31)));
    res.sm31 = add(sub(mul(lef.sm3, rig.al1), mul(lef.sm31, rig.al31)),
                   sub(mul(lef.eq3, rig.sm1), mul(lef.eq31, rig.sm31)));

    return res;
}

void build(int p, int l, int r){
    if (l == r)
        return void(tree[p] = node(arr[l]));

    int mid = (l+r)/2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);

    tree[p] = join(tree[2*p], tree[2*p+1]);

    //printf("l = %d, r = %d\n", l, r), tree[p].print();
}

void update(int p, int l, int r, int i, int v){
    if (l == r)
        return void(tree[p] = node(v));

    int mid = (l+r)/2;
    if (i <= mid)
        update(2*p, l, mid, i, v);
    else
        update(2*p+1, mid+1, r, i, v);

    tree[p] = join(tree[2*p], tree[2*p+1]);
}

node ask(int p, int l, int r, int i, int j){
    if (i <= l && r <= j)
        return tree[p];

    int mid = (l+r)/2;
    if (j <= mid)
        return ask(2*p, l, mid, i, j);
    if (i > mid)
        return ask(2*p+1, mid+1, r, i, j);

    return join(ask(2*p, l, mid, i, j), ask(2*p+1, mid+1, r, i, j));
}

int query(int i, int j){
    node cur = ask(1, 1, n, i, j);
    return add(cur.sm, cur.eq);
}

int main(){
    scanf("%d %d", &n, &q);
    scanf("%s", str);
    for (int i = 1; i <= n; i++)
        arr[i] = str[i-1] - '0';

    build(1, 1, n);

    printf("%d\n", query(1, n));
    while (q--){
        int t, i, j;
        scanf("%d %d %d", &t, &i, &j);
        if (t == 2)
            update(1, 1, n, i, j);
        else
            printf("%d\n", query(i, j));
    }
    return 0;
}

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
lucky.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |     scanf("%s", str);
      |     ~~~~~^~~~~~~~~~~
lucky.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |         scanf("%d %d %d", &t, &i, &j);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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