Submission #1207544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207544		Nursik	Sterilizing Spray (JOI15_sterilizing)	C++20	0 / 100	5093 ms	21848 KiB

sterilizing

#include <bits/stdc++.h>

#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define i128 __int128_t
#define ff first
#define ss second
#define pii pair<int, int>
#define _cnt __builtin_popcount
#define debug(x) cerr << #x << " " << x << "\n";
#define int ll

using namespace std;

const int maxn = 1e5 + 4, maxa = 5e6, inf = 2e9, maxp = 1234, mod = 1e9 + 7;
const ll infll = 1e18;
const double eps = 1e-9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int N = 1 << (__lg(maxn) + 1);
int k;
struct Segtree {
    int mn = 0, mx = 0, push = -1;
    ll sum = 0;
    int lb, rb;
    Segtree *l, *r;

    Segtree(int lb, int rb=N): lb(lb), rb(rb) {
        if (lb == rb - 1) {
            l = nullptr;
            r = nullptr;
            return; 
        }
        int m = lb + rb >> 1;
        l = new Segtree(lb, m);
        r = new Segtree(m, rb);
    }

    void make_push() {
        if (push == -1) {
            return;
        }

        l->sum = 1LL * (l->rb - l->lb + 1) * push;
        l->mn = l->mx = l->push = push;

        r->sum = 1LL * (r->rb - r->lb + 1) * push;
        r->mn = r->mx = r->push = push;

        push = -1;
    }

    void upd_pt(int pos, int val) {
        if (pos < lb || rb <= pos) {
            return;
        }

        if (lb == pos && pos == rb - 1) {
            sum = mn = mx = val;
            return;
        }

        make_push();

        l->upd_pt(pos, val);
        r->upd_pt(pos, val);
        
        sum = l->sum + r->sum;
        mn = min(l->mn, r->mn);
        mx = max(l->mx, r->mx);
    }

    void _upd_rng(int ql, int qr) {
        if (qr <= lb || rb <= ql || mx == 0) {
            return;
        }

        if (ql <= lb && rb <= qr && mn / k == mx / k) {
            int val = mn / k;
            sum = 1LL * val * (rb - lb + 1);
            mn = mx = val;
            push = val;
            return;
        }

        make_push();
        l->_upd_rng(ql, qr);
        r->_upd_rng(ql, qr);
        sum = l->sum + r->sum;
        mn = min(l->mn, r->mn);
        mx = max(l->mx, r->mx);
    }

    ll _get(int ql, int qr) {
        if (qr <= lb || rb <= ql) {
            return 0;
        }

        if (ql <= lb && rb <= qr) {
            return sum;
        }

        make_push();
        return l->_get(ql, qr) + r->_get(ql, qr);
    }

    ll get(int ql, int qr) {
        return _get(ql, qr + 1);
    }

    void upd_rng(int ql, int qr) {
        _upd_rng(ql, qr + 1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q >> k;

    vector<int> v(n);
    for (int &i : v) {
        cin >> i;
    }

    Segtree st(0, N);
    for (int i = 0; i < n; i++) {
        st.upd_pt(i, v[i]);
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            --pos;
            st.upd_pt(pos, val);
        } else if (type == 2) {
            int ql, qr;
            cin >> ql >> qr;
            --ql, --qr;
            st.upd_rng(ql, qr);   
        } else {
            int ql, qr;
            cin >> ql >> qr;
            --ql, --qr;
            cout << st.get(ql, qr) << "\n";
        }
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

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