Submission #1239805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239805		The_Samurai	Fish 3 (JOI24_fish3)	C++20	100 / 100	495 ms	98352 KiB

Main

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
const ll inf = 1e18;
using i128 = __int128_t;

struct segtree {
    struct node {
        int cnt;
        ll mn, lazy;
        i128 sum;

        node() {
            mn = lazy = inf;
            sum = cnt = 0;
        }

        void merge(const node &a, const node &b) {
            cnt = a.cnt + b.cnt;
            mn = min(a.mn, b.mn);
            sum = a.sum + b.sum;
        }

        void impact(ll v) {
            mn = v;
            sum = i128(v) * cnt;
            lazy = v;
        }

        void propagate(node &a, node &b) {
            if (lazy != inf) {
                a.impact(lazy);
                b.impact(lazy);
                lazy = inf;
            }
        }
    };

    vector<node> tree;
    node neutral_element;
    int size;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, neutral_element);
        for (int i = size - 1; i < size - 1 + n; i++) tree[i].cnt = 1;
        for (int i = size - 2; i >= 0; i--) tree[i].merge(tree[i * 2 + 1], tree[i * 2 + 2]);
    }

    void upd(int l, int r, ll v, int x, int lx, int rx) {
        if (l >= rx or lx >= r) return;
        if (l <= lx and rx <= r) {
            tree[x].impact(v);
            return;
        }
        tree[x].propagate(tree[x * 2 + 1], tree[x * 2 + 2]);
        int mid = (lx + rx) >> 1;
        upd(l, r, v, x * 2 + 1, lx, mid);
        upd(l, r, v, x * 2 + 2, mid, rx);
        tree[x].merge(tree[x * 2 + 1], tree[x * 2 + 2]);
    }

    void upd(int l, int r, ll v) {
        upd(l, r + 1, v, 0, 0, size);
    }

    node get(int l, int r, int x, int lx, int rx) {
        if (l >= rx or lx >= r) return neutral_element;
        if (l <= lx and rx <= r) return tree[x];
        tree[x].propagate(tree[x * 2 + 1], tree[x * 2 + 2]);
        int mid = (lx + rx) >> 1;
        node ans;
        ans.merge(get(l, r, x * 2 + 1, lx, mid), get(l, r, x * 2 + 2, mid, rx));
        return ans;
    }

    pair<i128, ll> get(int l, int r) {
        node ans = get(l, r + 1, 0, 0, size);
        return make_pair(ans.sum, ans.mn);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, q; ll d;
    cin >> n >> d;
    vector<ll> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];

    cin >> q;
    vector<vector<pair<int, int>>> queries(n + 1);
    vector<i128> ans(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        queries[r].emplace_back(l, i);
    }

    segtree sg; sg.init(n + 1);
    ll sub = 0;
    i128 sum = 0;
    set<pair<ll, int>, greater<>> st;
    vector<i128> pref_sub(n + 1), pref_sum(n + 1);
    for (int r = 1; r <= n; r++) {
        sub += (c[r] % d - c[r - 1] % d + d) % d;
        pref_sum[r] = pref_sum[r - 1] + c[r] - sub;
        pref_sub[r] = sub;
        int cnt = 1;
        while (!st.empty() and st.begin()->first >= c[r] - sub) {
            cnt += st.begin()->second;
            st.erase(st.begin());
        }
        st.emplace(c[r] - sub, cnt); sg.upd(r - cnt + 1, r, c[r] - sub);

        for (auto [l, i]: queries[r]) {
            auto it = sg.get(l, r);
            i128 add = pref_sub[l - 1];
            if (c[l - 1] % d > c[l] % d and l > 1) add += d - c[l - 1] % d;
            // cout << l << ' ' << r << ' ' << ll(it.ff) << ' ' << it.ss << ' ' << ll(add) << endl;
            if (it.ss + add < 0) ans[i] = -1;
            else {
                it.ff += add * (r - l + 1);
                i128 shit = pref_sum[r] - pref_sum[l - 1];
                shit += add * (r - l + 1);
                ans[i] = (shit - it.ff) / d;
            }
        }
    }
    
    for (i128 x: ans) cout << ll(x) << '\n';
}

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