Submission #122812

#	Time	Username	Problem	Language	Result	Execution time	Memory
122812		popovicirobert	Watering can (POI13_kon)	C++14	100 / 100	476 ms	29184 KiB

kon

#include <bits/stdc++.h>

using namespace std;

int N, K;

struct SegTree {

    const int INF = 1e9;

    struct Node {
        int mn, cnt;
        int lazy;
    };

    vector <Node> aint;
    int n;

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

    inline void solve_lazy(int nod) {
        if(2 * nod + 1 <= 4 * n) {
            aint[2 * nod].lazy += aint[nod].lazy;
            aint[2 * nod + 1].lazy += aint[nod].lazy;
        }
        aint[nod].lazy = 0;
    }

    inline void refresh(int nod) {
        aint[nod].cnt = aint[2 * nod].cnt + aint[2 * nod + 1].cnt;
        aint[nod].mn = min(aint[2 * nod].mn + aint[2 * nod].lazy, aint[2 * nod + 1].mn + aint[2 * nod + 1].lazy);
    }

    void build(int nod, int left, int right, int *D) {
        if(left == right) {
            aint[nod].mn = K - D[left - 1];
            if(aint[nod].mn <= 0) {
                aint[nod] = {INF, 1, 0};
            }
        }
        else {
            int mid = (left + right) / 2;

            build(2 * nod, left, mid, D);
            build(2 * nod + 1, mid + 1, right, D);

            refresh(nod);
        }
    }

    void update(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r && aint[nod].mn + aint[nod].lazy - 1 > 0) {
            aint[nod].lazy--;
            return ;
        }
        if(left == right) {
            aint[nod] = {INF, 1, 0};
            return ;
        }

        solve_lazy(nod);

        int mid = (left + right) / 2;

        if(l <= mid) update(2 * nod, left, mid, l, r);
        if(mid < r) update(2 * nod + 1, mid + 1, right, l, r);

        refresh(nod);
    }

    int query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod].cnt;
        }
        else {
            int mid = (left + right) / 2;
            int 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;
        }
    }
}st;

void inicjuj(int n, int k, int *D) {
    N = n, K = k;
    st.init(N);
    st.build(1, 1, N, D);
}

void podlej(int a, int b) {
    a++, b++;
    st.update(1, 1, N, a, b);
}

int dojrzale(int a, int b) {
    a++, b++;
    return st.query(1, 1, N, a, b);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10