oj.uz

Submission #799268

# Submission time Handle Problem Language Result Execution time Memory
799268 2023-07-31T11:29:54 Z Blagoj Watering can (POI13_kon) C++17
80 / 100
 270 ms 19400 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) {
        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 2 ms 1536 KB Output is correct
2 Correct 1 ms 1480 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 1620 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 4088 KB Output is correct
2 Correct 29 ms 3916 KB Output is correct
3 Correct 30 ms 3860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5452 KB Output is correct
2 Correct 49 ms 5612 KB Output is correct
3 Correct 44 ms 5596 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7180 KB Output is correct
2 Correct 57 ms 7340 KB Output is correct
3 Correct 75 ms 5660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 7716 KB Output is correct
2 Correct 92 ms 7640 KB Output is correct
3 Correct 117 ms 7116 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 7836 KB Output is correct
2 Correct 108 ms 10536 KB Output is correct
3 Correct 135 ms 7196 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 13504 KB Output is correct
2 Correct 173 ms 10732 KB Output is correct
3 Correct 222 ms 11484 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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