oj.uz

Submission #480130

# Submission time Handle Problem Language Result Execution time Memory
480130 2021-10-14T19:07:47 Z nicolaalexandra Lucky Numbers (RMI19_lucky) C++14
100 / 100
 62 ms 16284 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define MOD 1000000007
using namespace std;

long long dp[DIM];
int v[DIM];
char s[DIM];
int n,q,i,x,y,tip;

struct segment_tree{
    long long cnt; /// cate am in total
    long long cnt1; /// cate se termina cu 1
    long long cnt3; /// cate incep cu 3
    long long cnt31; /// cate incep cu 3 si se termina cu 1
    int ok,ok1,ok3,ok31; /// inf strict despre intervalul curent
    int sz; /// nr de cifre
} aint[DIM*4];


segment_tree update_nod (segment_tree fiu_st, segment_tree fiu_dr){

    segment_tree nod;

    nod.sz = fiu_st.sz + fiu_dr.sz;
    nod.ok = nod.ok1 = nod.ok3 = nod.ok31 = 0;
    if (!(fiu_st.ok1 && fiu_dr.ok3)){

        if (fiu_st.ok && fiu_dr.ok)
            nod.ok = 1;
        if (fiu_st.ok && fiu_dr.ok1)
            nod.ok1 = 1;
        if (fiu_st.ok3 && fiu_dr.ok)
            nod.ok3 = 1;
        if (fiu_st.ok3 && fiu_dr.ok1)
            nod.ok31 = 1;
    }

    /// mai mic strict stanga + orice in dreapta
    nod.cnt = (fiu_st.cnt - fiu_st.ok + MOD) * dp[fiu_dr.sz] % MOD;
    /// egal stanga, mai mic sau egal in dreapta
    nod.cnt = (nod.cnt + fiu_dr.cnt * fiu_st.ok) % MOD;

    nod.cnt = (nod.cnt - fiu_dr.cnt3 * fiu_st.ok1 % MOD + MOD) % MOD;
    nod.cnt = (nod.cnt - (fiu_st.cnt1 - fiu_st.ok1) * dp[ fiu_dr.sz - 1] % MOD + MOD) % MOD;


    nod.cnt1 = (fiu_st.cnt - fiu_st.ok + MOD) * dp[fiu_dr.sz - 1] % MOD;
    nod.cnt1 = (nod.cnt1 + fiu_dr.cnt1 * fiu_st.ok % MOD) % MOD;

    nod.cnt1 = (nod.cnt1 - (fiu_st.cnt1 - fiu_st.ok1) * dp[ fiu_dr.sz - 2 ] % MOD + MOD) % MOD;
    nod.cnt1 = (nod.cnt1 - fiu_st.ok1 * fiu_dr.cnt31 % MOD + MOD) % MOD;


    nod.cnt3 = (fiu_st.cnt3 - fiu_st.ok3 + MOD) * dp[fiu_dr.sz] % MOD;
    nod.cnt3 = (nod.cnt3 + fiu_dr.cnt * fiu_st.ok3 % MOD) % MOD;

    nod.cnt3 = (nod.cnt3 - (fiu_st.cnt31 - fiu_st.ok31) * dp[fiu_dr.sz-1] % MOD + MOD) % MOD;
    nod.cnt3 = (nod.cnt3 - fiu_st.ok31 * fiu_dr.cnt3 % MOD + MOD) % MOD;


    nod.cnt31 = (fiu_st.cnt3 - fiu_st.ok3 + MOD) * dp[fiu_dr.sz - 1] % MOD;
    nod.cnt31 = (nod.cnt31 + fiu_st.ok3 * fiu_dr.cnt1 % MOD) % MOD;

    nod.cnt31 = (nod.cnt31 - (fiu_st.cnt31 - fiu_st.ok31) * dp[fiu_dr.sz - 2] % MOD + MOD) % MOD;
    nod.cnt31 = (nod.cnt31 - fiu_st.ok31 * fiu_dr.cnt31 % MOD + MOD) % MOD;


    return nod;
}

void update_digit (int nod, int val){
    aint[nod].cnt = val+1;
    aint[nod].sz = 1;

    aint[nod].cnt1 = aint[nod].cnt3 = 1;
    if (val < 1)
        aint[nod].cnt1 = 0;
    if (val < 3)
        aint[nod].cnt3 = 0;

    aint[nod].cnt31 = 0;


    aint[nod].ok = 1, aint[nod].ok1 = aint[nod].ok3 = aint[nod].ok31 = 0;
    if (val == 1)
        aint[nod].cnt1 = aint[nod].ok1 = 1;
    if (val == 3)
        aint[nod].cnt3 = aint[nod].ok3 = 1;

}

void build (int nod, int st, int dr){
    if (st == dr){
        update_digit (nod,v[st]);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    aint[nod] = update_nod(aint[nod<<1],aint[(nod<<1)|1]);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        update_digit(nod,val);
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = update_nod(aint[nod<<1],aint[(nod<<1)|1]);
}

segment_tree query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y)
        return aint[nod];

    int mid = (st+dr)>>1;

    if (x > mid)
        return query ((nod<<1)|1,mid+1,dr,x,y);
    else {
        if (y <= mid)
            return query (nod<<1,st,mid,x,y);
        else return update_nod (query(nod<<1,st,mid,x,y),query((nod<<1)|1,mid+1,dr,x,y));
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>q;
    cin>>s+1;
    for (i=1;i<=n;i++)
        v[i] = s[i] - '0';

    /// dp[i] - cate nr bune de i cifre exista
    dp[0] = 1, dp[1] = 10;
    for (i=2;i<=n;i++)
        dp[i] = (dp[i-1] * 10 % MOD - dp[i-2] + MOD) % MOD;

    build (1,1,n);

    cout<<aint[1].cnt<<"\n";

    for (;q--;){
        cin>>tip>>x>>y;
        if (tip == 1)
            cout<<query (1,1,n,x,y).cnt<<"\n";
        else update (1,1,n,x,y);
    }

    return 0;
}

Compilation message

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

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 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 26 ms 1460 KB Output is correct
2 Correct 33 ms 2464 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1460 KB Output is correct
2 Correct 33 ms 2464 KB Output is correct
3 Correct 51 ms 15940 KB Output is correct
4 Correct 54 ms 15928 KB Output is correct
5 Correct 52 ms 16060 KB Output is correct
6 Correct 56 ms 16204 KB Output is correct
7 Correct 62 ms 16184 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 26 ms 1460 KB Output is correct
8 Correct 33 ms 2464 KB Output is correct
9 Correct 25 ms 1336 KB Output is correct
10 Correct 28 ms 2380 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 26 ms 1460 KB Output is correct
8 Correct 33 ms 2464 KB Output is correct
9 Correct 51 ms 15940 KB Output is correct
10 Correct 54 ms 15928 KB Output is correct
11 Correct 52 ms 16060 KB Output is correct
12 Correct 56 ms 16204 KB Output is correct
13 Correct 62 ms 16184 KB Output is correct
14 Correct 25 ms 1336 KB Output is correct
15 Correct 28 ms 2380 KB Output is correct
16 Correct 43 ms 15768 KB Output is correct
17 Correct 41 ms 16008 KB Output is correct
18 Correct 43 ms 16020 KB Output is correct
19 Correct 51 ms 16284 KB Output is correct
20 Correct 51 ms 16264 KB Output is correct