Submission #476192

#	Time	Username	Problem	Language	Result	Execution time	Memory
476192		iulia13	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	75 ms	10268 KiB

lucky

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int n, q;
char s[N];
int dp[N];
struct ura{
    int cnt, cnt1, cnt3, cnt31, are1, are3, are31, eok, nr;
    ///cnt -> cate cu prop aia
} seg[N * 4];
int adun(int a, int b)
{
    int c = a + b;
    if (c >= mod)
        c -= mod;
    return c;
}
int inm(int a, int b)
{
    ll aa = a;
    ll bb = b;
ll    c = aa * bb;
    c = c % mod;
    return c;
}
int scad(int a, int b)
{
    int c = a - b;
    if (c < 0)
        c += mod;
    return c;
}
ura join(ura a, ura b)
{
    ura rez;
    rez.are1 = rez.are31 = rez.are3 = rez.cnt1 = rez.cnt31 = rez.cnt3 = rez.cnt = rez.eok = rez.nr = 0;
    if (!(a.are1 && b.are3))
    {
        if (a.eok && b.eok)
            rez.eok = 1;
        if (a.are3 && b.are1)
            rez.are31 = 1;
        if (a.are3 && b.eok)
            rez.are3 = 1;
        if (b.are1 && a.eok)
            rez.are1 = 1;
    }
    rez.cnt = scad(adun(inm(scad(a.cnt, a.eok), dp[b.nr]), inm(a.eok, b.cnt)), adun(inm(scad(a.cnt1, a.are1), dp[b.nr - 1]), inm(b.cnt3, a.are1)));
    rez.cnt1 = scad(adun(inm(scad(a.cnt, a.eok), dp[b.nr - 1]), inm(b.cnt1, a.eok)), adun(inm(scad(a.cnt1, a.are1), dp[b.nr - 2]), inm(b.cnt31, a.are1)));
	rez.cnt3 = scad(adun(inm(scad(a.cnt3, a.are3), dp[b.nr]), inm(b.cnt, a.are3)), adun(inm(scad(a.cnt31, a.are31), dp[b.nr - 1]), inm(b.cnt3, a.are31)));
	rez.cnt31 = scad(adun(inm(scad(a.cnt3, a.are3), dp[b.nr - 1]), inm(b.cnt1, a.are3)), adun(inm(scad(a.cnt31, a.are31), dp[b.nr - 2]), inm(b.cnt31, a.are31)));
    rez.nr = adun(a.nr, b.nr);
    return rez;
}
void leaf(int nod, int val)
{
    seg[nod].are1 = seg[nod].are31 = seg[nod].are3 = seg[nod].cnt1 = seg[nod].cnt3 = seg[nod].cnt31 = 0;
    seg[nod].nr = 1;
    seg[nod].eok = 1;
    if (val == 1)
        seg[nod].are1 = 1;
    if (val == 3)
        seg[nod].are3 = 1;
    if (1 <= val)
        seg[nod].cnt1 = 1;
    if (3 <= val)
        seg[nod].cnt3 = 1;
    seg[nod].cnt = val + 1;
    return;
}
void upd(int nod, int l, int r, int poz, int val)
{
    if (l == r)
    {
        leaf(nod, val);
        return;
    }
    int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
    if (poz <= mid)
        upd(ls, l, mid, poz, val);
    else
        upd(rs, 1 + mid, r, poz, val);
    seg[nod] = join(seg[ls], seg[rs]);
}
ura qry(int nod, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return seg[nod];
    int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
    if (mid < ql)
        return qry(rs, mid + 1, r, ql, qr);
    else
    if (qr <= mid)
        return qry(ls, l, mid, ql, qr);
    else
        return join(qry(ls, l, mid, ql, qr), qry(rs, mid + 1, r, ql, qr));
}
void build(int nod, int l, int r)
{
    if (l == r)
    {
        leaf(nod, s[l] - '0');
        return;
    }
    int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    seg[nod] = join(seg[ls], seg[rs]);
}
int main()
{
    cin >> n >> q;
    cin >> s + 1;
    dp[0] = 1;
    dp[1] = 10;
    for (int i = 2; i <= n; i++)
        dp[i] = scad(inm(dp[i - 1], 10) , dp[i - 2]);
    build(1, 1, n);
    cout << qry(1, 1, n, 1, n).cnt << '\n';

    while (q--)
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1)
        {
            cout << qry(1, 1, n, a, b).cnt << '\n';
            continue;
        }
        upd(1, 1, n, a, b);
    }
    return 0;
}

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |     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