Submission #1250476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250476		NHristov	Fish 3 (JOI24_fish3)	C++20	100 / 100	433 ms	41808 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 3e5 + 5;

int n, t;
int d;

int c[N];
vector < pair < int, int > > queries[N];
int ans[N];

struct Node
{
    int val;
    int lazy;
};

struct Seggy
{
    Node tree[4 * N];

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        int mid = (l + r) / 2;

        tree[2 * node].val += (mid - l + 1) * tree[node].lazy;
        tree[2 * node + 1].val += (r - mid) * tree[node].lazy;

        tree[2 * node].lazy += tree[node].lazy;
        tree[2 * node + 1].lazy += tree[node].lazy;

        tree[node].lazy = 0;
    }

    void update(int node, int l, int r, int ql, int qr, int val)
    {
        if (l > qr || r < ql)
        {
            return;
        }

        if (ql <= l && r <= qr)
        {
            tree[node].val += (r - l + 1) * val;
            tree[node].lazy += val;

            return;
        }

        int mid = (l + r) / 2;

        push(node, l, r);

        update(2 * node, l, mid, ql, qr, val);
        update(2 * node + 1, mid + 1, r, ql, qr, val);

        tree[node].val = tree[2 * node].val + tree[2 * node + 1].val;
    }

    int query(int node, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
        {
            return 0;
        }

        if (ql <= l && r <= qr)
        {
            return tree[node].val;
        }

        int mid = (l + r) / 2;

        push(node, l, r);

        return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
};

Seggy segment;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> d;

    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
    }

    cin >> t;

    for (int i = 1; i <= t; i++)
    {
        int l, r;

        cin >> l >> r;

        queries[r].push_back({l, i});
    }

    stack < int > st;

    for (int i = 1; i <= n; i++)
    {
        int r = i;

        while (!st.empty())
        {
            int a = c[r - 1] - segment.query(1, 1, n, r - 1, r - 1) * d;
            int b = c[r] - segment.query(1, 1, n, r, r) * d;

            if (a <= b)
            {
                break;
            }

            int more = (a - b - 1) / d + 1;

            segment.update(1, 1, n, st.top(), r - 1, more);
            r = st.top();

            st.pop();
        }

        st.push(r);

        for (auto [l, id] : queries[i])
        {
            if (c[l] - segment.query(1, 1, n, l, l) * d < 0)
            {
                ans[id] = -1;
            }
            else
            {
                ans[id] = segment.query(1, 1, n, l, i);
            }
        }
    }

    for (int i = 1; i <= t; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

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