oj.uz

Submission #476192

# Submission time Handle Problem Language Result Execution time Memory
476192 2021-09-25T09:43:47 Z iulia13 Lucky Numbers (RMI19_lucky) C++14
100 / 100
 75 ms 10268 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 0 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 976 KB Output is correct
2 Correct 32 ms 1612 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 976 KB Output is correct
2 Correct 32 ms 1612 KB Output is correct
3 Correct 44 ms 10140 KB Output is correct
4 Correct 49 ms 10132 KB Output is correct
5 Correct 47 ms 10228 KB Output is correct
6 Correct 75 ms 10268 KB Output is correct
7 Correct 60 ms 10268 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 27 ms 976 KB Output is correct
8 Correct 32 ms 1612 KB Output is correct
9 Correct 25 ms 1056 KB Output is correct
10 Correct 29 ms 1612 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 27 ms 976 KB Output is correct
8 Correct 32 ms 1612 KB Output is correct
9 Correct 44 ms 10140 KB Output is correct
10 Correct 49 ms 10132 KB Output is correct
11 Correct 47 ms 10228 KB Output is correct
12 Correct 75 ms 10268 KB Output is correct
13 Correct 60 ms 10268 KB Output is correct
14 Correct 25 ms 1056 KB Output is correct
15 Correct 29 ms 1612 KB Output is correct
16 Correct 37 ms 10024 KB Output is correct
17 Correct 39 ms 10108 KB Output is correct
18 Correct 39 ms 10204 KB Output is correct
19 Correct 52 ms 10244 KB Output is correct
20 Correct 46 ms 10188 KB Output is correct