제출 #109838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109838		popovicirobert	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1224 ms	9600 KiB

sterilizing

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;



struct SegTree {

    struct Node {
        int mx, pos;
        ll sum;
    };

    vector <Node> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
    }

    inline void refresh(int nod) {
        if(aint[2 * nod].mx > aint[2 * nod + 1].mx) {
            aint[nod].mx = aint[2 * nod].mx;
            aint[nod].pos = aint[2 * nod].pos;
        }
        else {
            aint[nod].mx = aint[2 * nod + 1].mx;
            aint[nod].pos = aint[2 * nod + 1].pos;
        }
        aint[nod].sum = aint[2 * nod].sum + aint[2 * nod + 1].sum;
    }

    void update(int nod, int left, int right, int pos, int val) {
        if(left == right) {
            aint[nod] = {val, left, val};
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
            refresh(nod);
        }
    }

    pair <int, int> get(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            if(aint[nod].mx == 0) {
                return {0, 0};
            }
            if(left == right) {
                return {aint[nod].mx, left};
            }
            int mid = (left + right) / 2;
            if(aint[2 * nod].mx > 0) return get(2 * nod, left, mid, l, r);
            return get(2 * nod + 1, mid + 1, right, l, r);
        }
        else {
            int mid = (left + right) / 2;
            pair <int, int> ans = {0, 0};
            if(l <= mid) ans = get(2 * nod, left, mid, l, r);
            if(mid < r && ans.first == 0) ans = get(2 * nod + 1, mid + 1, right, l, r);
            return ans;
        }
    }

    ll query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod].sum;
        }
        else {
            int mid = (left + right) / 2;
            ll ans = 0;
            if(l <= mid) ans += query(2 * nod, left, mid, l, r);
            if(mid < r) ans += query(2 * nod + 1, mid + 1, right, l, r);
            return ans;
        }
    }

};


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, q, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> q >> k;

    SegTree st; st.init(n);

    for(i = 1; i <= n; i++) {
        int val;
        cin >> val;
        st.update(1, 1, n, i, val);
    }

    while(q > 0) {
        q--;

        int type, pos, val;
        int l, r;
        cin >> type;

        if(type == 1) {
            cin >> pos >> val;
            st.update(1, 1, n, pos, val);
        }

        if(type == 2) {
            cin >> l >> r;
            if(k == 1) {
                continue;
            }

            int pos = l;
            while(pos <= r) {
                pair <int, int> cur = st.get(1, 1, n, pos, r);
                if(cur.first == 0) {
                    break;
                }
                st.update(1, 1, n, cur.second, cur.first / k);
                pos = cur.second + 1;
            }
        }

        if(type == 3) {
            cin >> l >> r;
            cout << st.query(1, 1, n, l, r) << "\n";
        }

    }

    //cin.close();
    //cout.close();
    return 0;
}

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