oj.uz

Submission #109838

# Submission time Handle Problem Language Result Execution time Memory
109838 2019-05-08T06:59:31 Z popovicirobert Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1224 ms 9600 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 16 ms 640 KB Output is correct
6 Correct 13 ms 640 KB Output is correct
7 Correct 15 ms 640 KB Output is correct
8 Correct 16 ms 640 KB Output is correct
9 Correct 20 ms 640 KB Output is correct
10 Correct 13 ms 640 KB Output is correct
11 Correct 14 ms 640 KB Output is correct
12 Correct 14 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 5752 KB Output is correct
2 Correct 64 ms 4560 KB Output is correct
3 Correct 57 ms 7160 KB Output is correct
4 Correct 87 ms 9080 KB Output is correct
5 Correct 99 ms 9592 KB Output is correct
6 Correct 83 ms 9464 KB Output is correct
7 Correct 90 ms 9600 KB Output is correct
8 Correct 121 ms 9592 KB Output is correct
9 Correct 91 ms 9412 KB Output is correct
10 Correct 89 ms 9448 KB Output is correct
11 Correct 93 ms 9464 KB Output is correct
12 Correct 93 ms 9336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1152 KB Output is correct
2 Correct 35 ms 3456 KB Output is correct
3 Correct 45 ms 3704 KB Output is correct
4 Correct 76 ms 3192 KB Output is correct
5 Correct 137 ms 8028 KB Output is correct
6 Correct 130 ms 8056 KB Output is correct
7 Correct 99 ms 8248 KB Output is correct
8 Correct 136 ms 8184 KB Output is correct
9 Correct 139 ms 7944 KB Output is correct
10 Correct 115 ms 8060 KB Output is correct
11 Correct 115 ms 7972 KB Output is correct
12 Correct 112 ms 8100 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 5316 KB Output is correct
2 Correct 313 ms 5496 KB Output is correct
3 Correct 500 ms 4564 KB Output is correct
4 Correct 341 ms 4448 KB Output is correct
5 Correct 519 ms 9464 KB Output is correct
6 Correct 592 ms 9464 KB Output is correct
7 Correct 450 ms 9464 KB Output is correct
8 Correct 885 ms 9376 KB Output is correct
9 Correct 666 ms 9376 KB Output is correct
10 Correct 809 ms 9352 KB Output is correct
11 Correct 495 ms 9356 KB Output is correct
12 Correct 1224 ms 9464 KB Output is correct