제출 #799270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799270		Blagoj	Watering can (POI13_kon)	C++17	100 / 100	277 ms	18896 KiB

kon

#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 / 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