Submission #865737

#	Time	Username	Problem	Language	Result	Execution time	Memory
865737		Cookie	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	42 ms	25696 KiB

lucky

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("nondec.in");
ofstream fout("nondec.out");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const ll mxn = 1e5 + 5, mxq = 2e5 + 5, sq = 500, mxv = 1e7 + 5;
const ll inf = 1e9;
const ld prec = 1e-5;
//const int base= (1 << 18);
struct Node{
    ll sm[2][2] = {}, eq[2][2] = {}, bg[2][2] = {};
    // [one][three] one at end,  three at beginning
    void init(int x){
        sm[0][0] = x - (x > 1) - (x > 3);
        sm[0][1] = x > 3;
        sm[1][0] = x > 1;
        eq[0][0] = (x != 1) && (x != 3);
        eq[0][1] = (x == 3); 
        eq[1][0] = (x == 1);
        bg[0][0] = 9 - x - (x < 3) - (x < 1);
        bg[0][1] = x < 3;
        bg[1][0] = x < 1;
    }
};
Node st[4 * mxn + 1];
char c[mxn + 1];
void add(ll &a, ll b){
    a += b;
    if(a >= mod)a %= mod;
}
Node comb(Node a, Node b){
    Node res; 
    forr(i, 0, 2){
        forr(j, 0, 2){
            forr(k, 0, 2){
                forr(l, 0, 2){
                    if(i == 1 && l == 1)continue;
                    add(res.sm[k][j], a.sm[i][j] * (b.sm[k][l] + b.eq[k][l] + b.bg[k][l]));
                    add(res.sm[k][j], a.eq[i][j] * b.sm[k][l]);
                    add(res.eq[k][j], a.eq[i][j] * b.eq[k][l]);
                    add(res.bg[k][j], a.bg[i][j] * (b.sm[k][l] + b.eq[k][l] + b.bg[k][l]));
                    add(res.bg[k][j], a.eq[i][j] * b.bg[k][l]);
                }
            }
        }
    }
    return(res);
}
int n, q;
void build(int nd, int l, int r){
    if(l == r){
        st[nd].init(c[l] - '0');
        return;
    }
    int mid = (l + r) >> 1;
    build(nd << 1, l, mid); build(nd << 1 | 1, mid + 1, r);
    st[nd] = comb(st[nd << 1], st[nd << 1 | 1]);
}
void upd(int nd, int l, int r, int id, int x){
    if(l == r){
        st[nd].init(x);
        return;
    }
    int mid = (l + r) >> 1;
    if(id <= mid)upd(nd << 1, l, mid, id, x); 
    else upd(nd << 1 | 1, mid + 1, r, id, x);
    st[nd] = comb(st[nd << 1], st[nd << 1 | 1]);
}
Node get(int nd, int l, int r, int ql, int qr){
    
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    if(qr <= mid)return(get(nd << 1, l, mid, ql, qr));
    else if(ql > mid)return(get(nd << 1 | 1, mid + 1, r, ql, qr));
    return(comb(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> c[i];
    }
    build(1, 1, n);
    ll ans = 0;
    forr(i, 0, 2){
        forr(j, 0, 2){
            add(ans, st[1].sm[i][j]);
            add(ans, st[1].eq[i][j]);
            
        }
    }
    Node curr = get(1, 1, n, 1, 2);
   
    cout << ans << "\n";
    while(q--){
        int idq; cin >> idq;
        if(idq == 2){
            int id, x; cin >> id >> x;
            upd(1, 1, n, id, x);
        }else{
            int l, r; cin >> l >> r;
            
            Node res = get(1, 1, n, l, r);
            
            ans = 0;
            forr(i, 0, 2){
                forr(j, 0, 2){
                    
                    add(ans, res.sm[i][j]);
                    add(ans, res.eq[i][j]);
                }
                
            }
            cout << ans << "\n";
            
        }
    }
    return(0);
}

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:109:10: warning: variable 'curr' set but not used [-Wunused-but-set-variable]
  109 |     Node curr = get(1, 1, n, 1, 2);
      |          ^~~~

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