Help Post on (MULTQ3 — Multiples of 3) [SPOJ]

Revision en2, by Muhammad_DinIslam, 2023-05-26 22:22:05
Where is the mistake? And where need to change? Please Help me.....
[Problem Link:](https://www.spoj.com/problems/MULTQ3/)
const int mxN = 1e5 + 10;
ll v[mxN], st[4 * mxN], lz[4 * mxN];
bool isMul(int x) {
    return (x % 3 == 0);
}
void build(int s, int e, int i = 1) {
    if (s == e) st[i] = isMul(v[s]);
    else {
        int mid = (s + e) / 2;
        build(s, mid, i * 2);
        build(mid + 1, e, i * 2 + 1);
        st[i] = st[i * 2] + st[i * 2 + 1];
    }
}
void lazy(int s, int e, int i) {
    st[i] = isMul(lz[i]) * (e - s + 1);
    if (s != e)
        lz[i * 2] += lz[i], lz[i * 2 + 1] += lz[i];
    lz[i] = 0;
}
ll query(int s, int e, int lb, int rb, int i = 1) {
    if (lz[i]) lazy(s, e, i);
    if (s > rb || e < lb) return 0ll;
    if (s >= lb && e <= rb) return st[i];
    int mid = (s + e) / 2;
    ll a = query(s, mid, lb, rb, i * 2);
    ll b = query(mid + 1, e, lb, rb, i * 2 + 1);
    return a + b;
}
void update(int s, int e, int lb, int rb, ll val, int i = 1) {
    if (lz[i]) lazy(s, e, i);
    if (s > rb || e < lb) return;
    if (s >= lb && e <= rb) {
        st[i] += isMul(val * (e - s + 1));
        // lz[i] = isMul(val * (e - s + 1));
        if (s != e)
            lz[i * 2] += val, lz[i * 2 + 1] += val;
    }
    else {
        int mid = (s + e) / 2;
        update(s, mid, lb, rb, val, i * 2);
        update(mid + 1, e, lb, rb, val, i * 2 + 1);
        st[i] = st[i * 2] + st[i * 2 + 1];
    }
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Muhammad_DinIslam 2023-05-26 22:22:05 60
en1 English Muhammad_DinIslam 2023-05-26 22:20:38 1592 Initial revision (published)