Submission #1275245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275245		reginox	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	245 ms	14200 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegTree {
    struct Node {
        ll sum;
        ll mx, mn;
        ll assign;
        Node(): sum(0), mx(0), mn(0), assign(-1) {}
    };
    int n;
    ll K;
    vector<Node> st;
    SegTree(int n_, ll K_, const vector<ll>& a): n(n_), K(K_) {
        st.assign(4*n+5, Node());
        build(1, 1, n, a);
    }
    void pull(int p) {
        st[p].sum = st[p<<1].sum + st[p<<1|1].sum;
        st[p].mx  = max(st[p<<1].mx, st[p<<1|1].mx);
        st[p].mn  = min(st[p<<1].mn, st[p<<1|1].mn);
        st[p].assign = -1;
    }
    void apply_assign(int p, int l, int r, ll val) {
        st[p].assign = val;
        st[p].mx = st[p].mn = val;
        st[p].sum = val * (r - l + 1);
    }
    void push(int p, int l, int r) {
        if (st[p].assign != -1 && l < r) {
            int m = (l + r) >> 1;
            apply_assign(p<<1, l, m, st[p].assign);
            apply_assign(p<<1|1, m+1, r, st[p].assign);
            st[p].assign = -1;
        }
    }
    void build(int p, int l, int r, const vector<ll>& a) {
        st[p].assign = -1;
        if (l == r) {
            ll v = a[l];
            st[p].sum = st[p].mx = st[p].mn = v;
            return;
        }
        int m = (l + r) >> 1;
        build(p<<1, l, m, a);
        build(p<<1|1, m+1, r, a);
        pull(p);
    }
    void point_set(int p, int l, int r, int pos, ll val) {
        if (l == r) {
            apply_assign(p, l, r, val);
            return;
        }
        push(p, l, r);
        int m = (l + r) >> 1;
        if (pos <= m) point_set(p<<1, l, m, pos, val);
        else point_set(p<<1|1, m+1, r, pos, val);
        pull(p);
    }
    void range_div(int p, int l, int r, int L, int R) {
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            ll tmx = st[p].mx / K;
            ll tmn = st[p].mn / K;
            if (tmx == tmn) {
                apply_assign(p, l, r, tmx);
                return;
            }
            if (l == r) {
                ll newv = st[p].mx / K;
                apply_assign(p, l, r, newv);
                return;
            }
        }
        if (l == r) return;
        push(p, l, r);
        int m = (l + r) >> 1;
        range_div(p<<1, l, m, L, R);
        range_div(p<<1|1, m+1, r, L, R);
        pull(p);
    }
    ll query_sum(int p, int l, int r, int L, int R) {
        if (R < l || r < L) return 0;
        if (L <= l && r <= R) return st[p].sum;
        push(p, l, r);
        int m = (l + r) >> 1;
        return query_sum(p<<1, l, m, L, R) + query_sum(p<<1|1, m+1, r, L, R);
    }
    void point_set(int pos, ll val) { point_set(1,1,n,pos,val); }
    void range_div(int L, int R) {
        if (K == 1) return;
        range_div(1,1,n,L,R);
    }
    ll query_sum(int L, int R) { return query_sum(1,1,n,L,R); }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    long long K;
    if (!(cin >> N >> Q >> K)) return 0;
    vector<long long> C(N+1);
    for (int i = 1; i <= N; ++i) cin >> C[i];

    SegTree st(N, K, C);

    for (int i = 0; i < Q; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int a; long long b;
            cin >> a >> b;
            st.point_set(a, b);
        } else if (op == 2) {
            int l, r; cin >> l >> r;
            st.range_div(l, r);
        } else if (op == 3) {
            int l, r; cin >> l >> r;
            cout << st.query_sum(l, r) << '\n';
        }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75