oj.uz

Submission #799270

# Submission time Handle Problem Language Result Execution time Memory
799270 2023-07-31T11:32:46 Z Blagoj Watering can (POI13_kon) C++17
100 / 100
 277 ms 18896 KB 
#include <bits/stdc++.h>
using namespace std;

int n, k, t[300005];
 
struct SegmentTree {
    int lzy[4 * 300005], cnt[4 * 300005], mn[4 * 300005];
    
    void build(int k = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            if (t[l] > 0) mn[k] = t[l];
            else {
                mn[k] = INT_MAX;
                cnt[k] = 1;
            }
            return;
        }
        build(k * 2, l, (l + r) / 2);
        build(k * 2 + 1, (l + r) / 2 + 1, r);
        cnt[k] = cnt[k * 2] + cnt[k * 2 + 1];
        mn[k] = min(mn[k * 2], mn[k * 2 + 1]);
    }

    void push(int k, int l, int r) {
        mn[k] -= lzy[k];
        if (l != r) {
            lzy[k * 2] += lzy[k];
            lzy[k * 2 + 1] += lzy[k];
        } 
        lzy[k] = 0;
    }

    void update(int k, int l, int r, int i, int j) {
        push(k, l, r);
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            lzy[k]++;
            push(k, l, r);
            return;
        }
        update(k * 2, l, (l + r) / 2, i, j);
        update(k * 2 + 1, (l + r) / 2 + 1, r, i, j);
        cnt[k] = cnt[k * 2] + cnt[k * 2 + 1];
        mn[k] = min(mn[k * 2], mn[k * 2 + 1]);
    }

    void rebuild(int k = 1, int l = 0, int r = n - 1) {
        push(k, l, r);
        if (mn[k] > 0) return;
        if (l == r) {
            mn[k] = INT_MAX;
            cnt[k] = 1;
            return;
        }
        rebuild(k * 2, l, (l + r) / 2);
        rebuild(k * 2 + 1, (l + r) / 2 + 1, r);
        cnt[k] = cnt[k * 2] + cnt[k * 2 + 1];
        mn[k] = min(mn[k * 2], mn[k * 2 + 1]);
    }

    int get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return cnt[k];
        return get(k * 2, l, (l + r) / 2, i, j) + get(k * 2 + 1, (l + r) / 2 + 1, r, i, j);
    }

} sgt;

void inicjuj(int _n, int _k, int *D)
{
    n = _n, k = _k;
    for (int i = 0; i < n; i++) t[i] = k - D[i];
    sgt.build();
}
 
void podlej(int a, int b)
{
    sgt.update(1, 0, n - 1, a, b);
    sgt.rebuild();
}
 
int dojrzale(int a, int b)
{
    return sgt.get(1, 0, n - 1, a, b);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2580 KB Output is correct
2 Correct 29 ms 2420 KB Output is correct
3 Correct 34 ms 2260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3368 KB Output is correct
2 Correct 48 ms 3204 KB Output is correct
3 Correct 43 ms 3336 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5216 KB Output is correct
2 Correct 55 ms 5324 KB Output is correct
3 Correct 65 ms 3572 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 5788 KB Output is correct
2 Correct 90 ms 5724 KB Output is correct
3 Correct 112 ms 5120 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 5928 KB Output is correct
2 Correct 105 ms 8504 KB Output is correct
3 Correct 136 ms 5212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 9648 KB Output is correct
2 Correct 169 ms 8652 KB Output is correct
3 Correct 212 ms 9380 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 16216 KB Output is correct
2 Correct 254 ms 18512 KB Output is correct
3 Correct 277 ms 16332 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 16360 KB Output is correct
2 Correct 248 ms 18896 KB Output is correct
3 Correct 251 ms 16396 KB Output is correct