Submission #1243360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243360		CrabCNH	Fish 3 (JOI24_fish3)	C++20	100 / 100	517 ms	44068 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define pii pair <int, int>

using namespace std;

const int maxN = 3e5 + 5;

int n, D;
int c[maxN];
int res[maxN];
vector <pii> off[maxN];

struct ST {
    vector <int> st, lazy;

    inline void init (int _n) {
        st.resize (_n * 4, 0LL);
        lazy.resize (_n * 4, 0LL);
    }

    inline void push (int id, int l, int r) {
        int &t = lazy[id];
        if (t != 0) {
            int mid = (l + r) >> 1;
            st[id * 2] += (mid - l + 1) * t;
            lazy[id * 2] += t;
            st[id * 2 + 1] += (r - (mid + 1) + 1) * t;
            lazy[id * 2 + 1] += t;
        }
        t = 0;
        return;
    }

    void upd (int id, int l, int r, int u, int v, int val) {
        if (v < l || u > r) {
            return;
        }
        if (u <= l && r <= v) {
            st[id] += (r - l + 1) * val;
            lazy[id] += val;
            return;
        }
        push (id, l, r);
        int mid = (l + r) >> 1;
        upd (id * 2, l, mid, u, v, val);
        upd (id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = (st[id * 2] + st[id * 2 + 1]);
        return;
    }

    int get (int id, int l, int r, int u, int v) {
        if (v < l || u > r) {
            return 0;
        }
        if (u <= l && r <= v) {
            return st[id];
        }
        push (id, l, r);
        int mid = (l + r) >> 1;
        int tL = get (id * 2, l, mid, u, v);
        int tR = get (id * 2 + 1, mid + 1, r, u, v);
        return (tL + tR);
    }
};

ST T;

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> D;
    T.init (n);
    for (int i = 1; i <= n; i ++) {
        cin >> c[i];
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i ++) {
        int l, r;
        cin >> l >> r;
        off[r].push_back ({l, i});
    }
    stack <int> st;
    for (int i = 1; i <= n; i ++) {
        int cur = i;
        while (!st.empty ()) {
            int x = c[cur - 1] - D * T.get (1, 1, n, cur - 1, cur - 1);
            int y = c[cur] - D * T.get (1, 1, n, cur, cur);
            if (x <= y) {
                break;
            }
            int need = (x - y - 1) / D + 1;
            T.upd (1, 1, n, st.top (), cur - 1, need);
            cur = st.top ();
            st.pop ();
        }
        st.push (cur);
        for (auto [l, id] : off[i]) {
            if ((c[l] - D * T.get (1, 1, n, l, l)) < 0) {
                res[id] = -1;
            }
            else {
                res[id] = T.get (1, 1, n, l, i);
            }
        }
    }
    for (int i = 1; i <= q; i ++) {
        cout << res[i] << '\n';
    }
}

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