Submission #952401

#	Time	Username	Problem	Language	Result	Execution time	Memory
952401		SulA	Sterilizing Spray (JOI15_sterilizing)	C++17	5 / 100	5059 ms	12084 KiB

sterilizing

#include <bits/stdc++.h>
#define push push_back
using namespace std;

long long oper(long long a, long long b) { return a + b; }

struct SEG {
    vector<long long> tree, lazy;
    int offset = 1;
    void init(int n) {
        while (offset < n) offset <<= 2;
        tree.resize(2*offset);
        lazy.resize(2*offset);
    }

    void pointupdate(int i, long long x) {
        i += offset;
        tree[i] = x;
        while (i /= 2) tree[i] = oper(tree[2*i], tree[2*i+1]);
    }

    long long _query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (r < ql || qr < l) return 0;
        int mid = (l+r)/2;
        return oper(_query(2*v, l, mid, ql, qr),
                    _query(2*v+1, mid+1, r, ql, qr));
    }

    long long query(int ql, int qr) {
        return _query(1, 0, offset-1, ql, qr);
    }

    void lazyupdate(int v, int l, int r, int ul, int ur, int k) {
        if (r < ul || ur < l) return;
        if (l == r) {
            tree[v] /= k;
            return;
        }
        int mid = (l+r)/2;
        lazyupdate(2*v, l, mid, ul, ur, k);
        lazyupdate(2*v+1, mid+1, r, ul, ur, k);
        tree[v] = oper(tree[2*v], tree[2*v+1]);
    }
};


int main () {
    int n,q,k; cin >> n >> q >> k;
    SEG s; s.init(n);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        s.pointupdate(i, x);
    }
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int i; long long x; cin >> i >> x;
            s.pointupdate(--i, x);
        }
        else if (type == 2) {
            int l,r; cin >> l >> r;
            s.lazyupdate(1, 0, s.offset-1, --l, --r, k);
        }
        else {
            int l,r; cin >> l >> r;
            cout << s.query(--l, --r) << "\n";
        }
    }
}

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