Submission #1237711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237711		t_holl	Fish 3 (JOI24_fish3)	C++20	100 / 100	742 ms	101224 KiB

Main

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

struct monoid {
    int sum = 0;
    int size = 1;
    int left = 0;
    int right = 0;
};
struct operation {
    int delta = 0;
};
monoid merge (monoid &a, monoid &b) {
    return { a.sum + b.sum, a.size + b.size, a.left, b.right };
}
operation chain (operation &a, operation &b) {
    return { a.delta + b.delta };
}
monoid apply (monoid &a, operation &b) {
    return { a.sum + b.delta * a.size, a.size, a.left, a.right };
}

struct SegTree {
    vector<monoid> tree;
    vector<operation> ops;

    int size, start, height;

    SegTree (int _size) {
        size = _size;
        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1, { 0, 1 });
        ops.resize(start << 1);

        for (int i = start; i < tree.size(); i ++) {
            tree[i] = {0, 1, i - start, i - start};
        }

        for (int i = start - 1; i > 0; i --)
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    void propagate (int node) {
        tree[node] = apply(tree[node], ops[node]);

        if (node < start) {
            ops[2 * node] = chain(ops[2 * node], ops[node]);
            ops[2 * node + 1] = chain(ops[2 * node + 1], ops[node]);
        }

        ops[node] = { 0 };
    }

    void update (int node, int ql, int qr, operation op) {
        propagate(node);

        if (qr < tree[node].left || tree[node].right < ql) return ;
        if (ql <= tree[node].left && tree[node].right <= qr) {
            ops[node] = chain(ops[node], op);
            propagate(node);
            return ;
        }

        update(2 * node, ql, qr, op);
        update(2 * node + 1, ql, qr, op);
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }
    void add (int ql, int qr, int del) {
        update(1, ql, qr, { del });
    }
    int sum (int ql, int qr, int node = 1) {
        propagate(node);

        if (qr < tree[node].left || tree[node].right < ql) return 0;
        if (ql <= tree[node].left && tree[node].right <= qr) {
            return tree[node].sum;
        }

        return sum(ql, qr, 2 * node) + sum(ql, qr, 2 * node + 1);
    }

    void show_tree () {
        for (int i = 1; i < tree.size(); i ++) {
            cout << tree[i].sum << "+(" << ops[i].delta << ")[" << tree[i].left << ";" << tree[i].right << "](" << tree[i].size << ") ";
        }
        cout << endl;
    }
};

struct query {
    int l, r;
    int id;

    bool operator< (const query &other) const {
        return r < other.r;
    }
};

void solve () {
    int N; cin >> N;
    int D; cin >> D;

    vector<int> A(N);
    for (int & a : A) cin >> a;

    int Q;
    cin >> Q;

    vector<query> queries;
    for (int i = 0; i < Q; i ++) {
        int l, r;
        cin >> l >> r;
        queries.push_back({ l - 1, r - 1, i });
    }

    sort(queries.rbegin(), queries.rend());

    vector<int> answers(Q, -1);

    vector<int> breaks;

    SegTree value_tree (N);
    SegTree cost_tree  (N);

    for (int i = 0; i < N; i ++) {
        value_tree.add(i, i, A[i]);
    }

    for (int r = 0; r < N; r ++) {
        breaks.push_back(r);
        while (breaks.size() >= 2) {
            int bp = breaks[breaks.size() - 2];
            int bm  = breaks.back() - 1;

            int vm = value_tree.sum(bm, bm);
            int vl = value_tree.sum(bm + 1, bm + 1);

            int delta = vm - vl;
            if (delta <= - D) break ;

            int cnt = (delta + D - 1) / D;

            value_tree.add(bp, bm, - cnt * D);
            cost_tree .add(bp, bm, cnt);
            
            breaks.pop_back();
        }

        while (queries.size() != 0 && queries.back().r == r) {
            query q = queries.back();
            queries.pop_back();

            if (value_tree.sum(q.l, q.l) >= 0) {
                answers[q.id] = cost_tree.sum(q.l, q.r);
            }
        }
    }

    for (int u : answers) cout << u << "\n";
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36