oj.uz

Submission #799269

# Submission time Handle Problem Language Result Execution time Memory
799269 2023-07-31T11:30:27 Z Blagoj Watering can (POI13_kon) C++17
80 / 100
 255 ms 14652 KB 
#include <bits/stdc++.h>
using namespace std;

int n, k, t[300005];
 
struct SegmentTree {
    int lzy[3 * 300005], cnt[3 * 300005], mn[3 * 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) {
        if (mn[k] != INT_MAX) 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 2 ms 1492 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 31 ms 2572 KB Output is correct
2 Correct 30 ms 2428 KB Output is correct
3 Correct 33 ms 2256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3412 KB Output is correct
2 Correct 51 ms 3208 KB Output is correct
3 Correct 43 ms 3344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5188 KB Output is correct
2 Correct 57 ms 5324 KB Output is correct
3 Correct 72 ms 3656 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 5788 KB Output is correct
2 Correct 88 ms 5692 KB Output is correct
3 Correct 113 ms 5160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 6004 KB Output is correct
2 Correct 106 ms 8528 KB Output is correct
3 Correct 133 ms 5244 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 9628 KB Output is correct
2 Correct 179 ms 8652 KB Output is correct
3 Correct 211 ms 9312 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 14652 KB Output isn't correct
2 Halted 0 ms 0 KB -