oj.uz

Submission #478014

# Submission time Handle Problem Language Result Execution time Memory
478014 2021-10-05T05:39:34 Z stefantaga Lucky Numbers (RMI19_lucky) C++14
100 / 100
 52 ms 10072 KB 
#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

lucky.cpp: In function 'int main()':
lucky.cpp:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |     cin >> s + 1;
      |            ~~^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 948 KB Output is correct
2 Correct 31 ms 1560 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 948 KB Output is correct
2 Correct 31 ms 1560 KB Output is correct
3 Correct 46 ms 9976 KB Output is correct
4 Correct 41 ms 9996 KB Output is correct
5 Correct 52 ms 9960 KB Output is correct
6 Correct 52 ms 10072 KB Output is correct
7 Correct 51 ms 10036 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 26 ms 948 KB Output is correct
8 Correct 31 ms 1560 KB Output is correct
9 Correct 20 ms 956 KB Output is correct
10 Correct 28 ms 1564 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 26 ms 948 KB Output is correct
8 Correct 31 ms 1560 KB Output is correct
9 Correct 46 ms 9976 KB Output is correct
10 Correct 41 ms 9996 KB Output is correct
11 Correct 52 ms 9960 KB Output is correct
12 Correct 52 ms 10072 KB Output is correct
13 Correct 51 ms 10036 KB Output is correct
14 Correct 20 ms 956 KB Output is correct
15 Correct 28 ms 1564 KB Output is correct
16 Correct 38 ms 9932 KB Output is correct
17 Correct 33 ms 9940 KB Output is correct
18 Correct 41 ms 9932 KB Output is correct
19 Correct 46 ms 10032 KB Output is correct
20 Correct 45 ms 10040 KB Output is correct