제출 #1239351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239351		eirinayukari	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	120 ms	7496 KiB

sterilizing

// XD XD
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el cout << "\n";

using namespace std;
using ll = long long;

const int MAXN = 1e6 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;

template <typename T>
bool ckmin(T& a, T b) {
    return a > b ? a = b, true : false;
}

template <typename T>
bool ckmax(T& a, T b) {
    return a < b ? a = b, true : false;
}

struct segmentTree {
    struct Node {
        ll sum;
        int mx;
        Node(ll _sum = 0, int _mx = 0) {
            sum = _sum;
            mx = _mx;
        }

        Node operator+(const Node &other) {
            Node res;
            res.sum = sum + other.sum;
            res.mx = max(mx, other.mx);
            return res;
        }
    };
    
    int n;
    vector<Node> tree;
    segmentTree(int _n, vector<int> &a) {
        n = _n; 
        tree.resize(4 * n + 1);
        build(a);
    }

    void build(int id, int l, int r, vector<int> &a) {
        if (l == r) {
            tree[id] = Node(a[l], a[l]);
            return;
        }

        int mid = l + r >> 1;
        build(id << 1, l, mid, a);
        build(id << 1 | 1, mid + 1, r, a);
        tree[id] = tree[id << 1] + tree[id << 1 | 1];
    }

    void build(vector<int> &a) {
        build(1, 1, n, a);
    }

    void update(int id, int l, int r, int u, int v, int k) {
        if (l > v || u > r) {
            return;
        }

        if (u <= l && r <= v) {
            if (tree[id].mx == 0) {
                return;
            }

            if (l == r) {
                int g = tree[id].mx;
                g /= k;
                tree[id] = Node(g, g);
                return;
            }
        }

        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v, k);
        update(id << 1 | 1, mid + 1, r, u, v, k);
        tree[id] = tree[id << 1] + tree[id << 1 | 1];
    }
    
    void update(int l, int r, int k) {
        update(1, 1, n, l, r, k);
    }

    void updateAssign(int id, int l, int r, int p, int v) {
        if (l == r) {
            tree[id] = Node(v, v);
            return;
        }

        int mid = l + r >> 1;
        if (p <= mid) {
            updateAssign(id << 1, l, mid, p, v);
        } else {
            updateAssign(id << 1 | 1, mid + 1, r, p, v);
        }
        tree[id] = tree[id << 1] + tree[id << 1 | 1];
    }

    void updateAssign(int p, int v) {
        updateAssign(1, 1, n, p, v);
    }

    ll get(int id, int l, int r, int u, int v) {
        if (l > v || u > r) {
            return 0;
        }

        if (u <= l && r <= v) {
            return tree[id].sum;
        }

        int mid = l + r >> 1;
        ll L = get(id << 1, l, mid, u, v);
        ll R = get(id << 1 | 1, mid + 1, r, u, v);
        return L + R;
    }

    ll get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

void solve(int id) {
    // cout << "Case " << id << ": ";
    int n, q, k;
    cin >> n >> q >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    segmentTree st(n, a);
    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            st.updateAssign(x, y);
        } else if (type == 2) {
            if (k != 1) {
                st.update(x, y, k);
            }
        } else {
            cout << st.get(x, y) << "\n";
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

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