oj.uz

Submission #122812

# Submission time Handle Problem Language Result Execution time Memory
122812 2019-06-29T10:21:45 Z popovicirobert Watering can (POI13_kon) C++14
100 / 100
 476 ms 29184 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3576 KB Output is correct
2 Correct 49 ms 3064 KB Output is correct
3 Correct 49 ms 3392 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4600 KB Output is correct
2 Correct 83 ms 5272 KB Output is correct
3 Correct 70 ms 4904 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 8180 KB Output is correct
2 Correct 95 ms 7160 KB Output is correct
3 Correct 110 ms 7032 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 13560 KB Output is correct
2 Correct 157 ms 9708 KB Output is correct
3 Correct 184 ms 11712 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 14176 KB Output is correct
2 Correct 184 ms 13688 KB Output is correct
3 Correct 234 ms 14456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 21624 KB Output is correct
2 Correct 304 ms 20052 KB Output is correct
3 Correct 361 ms 23032 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 27600 KB Output is correct
2 Correct 383 ms 27248 KB Output is correct
3 Correct 411 ms 27128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 28508 KB Output is correct
2 Correct 476 ms 29184 KB Output is correct
3 Correct 407 ms 28164 KB Output is correct