제출 #1279994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279994		tvgk	Fish 3 (JOI24_fish3)	C++20	9 / 100	2094 ms	9672 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e5 + 7, nB = 3e5;
const ll inf = 1e18;

int n, l[mxN], r[mxN], q;
ll dif, a[mxN], ans[mxN];
vector<int> query[mxN];

bool cmp(int u, int v)
{
    return r[u] < r[v];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> dif;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> l[i] >> r[i];

        if (l[i] / nB == r[i] / nB)
        {
            ll cur = inf;
            for (; r[i] >= l[i]; r[i]--)
            {
                ll tmp = 0;
                if (a[r[i]] > cur)
                    tmp = (a[r[i]] - cur + dif - 1) / dif;
                ans[i] += tmp;
                cur = a[r[i]] - tmp * dif;

                if (cur < 0)
                {
                    ans[i] = -1;
                    break;
                }
            }
        }
        else
            query[l[i] / nB].push_back(i);
    }

    for (int i = 0; i <= n / nB; i++)
    {
        sort(query[i].begin(), query[i].end(), cmp);

        ii cur = {0, 0};
        ll sum = 0, mem = 0;
        int ctr = nB * (i + 1);
        stack<ii> stk;
        for (int id : query[i])
        {
            while (ctr <= r[id])
            {
                if (a[ctr] % dif < cur.se)
                    cur.fi++;
                else
                    cur.se = a[ctr] % dif;

                int l = i;
                ll tmp = a[ctr] / dif - cur.fi;
                while (stk.size() && stk.top().se >= tmp)
                {
                    sum += (l - stk.top().fi) * (stk.top().se - tmp);
                    l = stk.top().fi;
                    stk.pop();
                }
                if (stk.empty())
                    mem = tmp;
                stk.push({l, tmp});

                ctr++;
            }

            ans[id] = sum;
            ll cur = mem * dif + a[nB * (i + 1)] % dif;
            for (int j = nB * (i + 1) - 1; j >= l[i]; j--)
            {
                ll tmp = 0;
                if (a[j] > cur)
                    tmp = (a[j] - cur + dif - 1) / dif;
                ans[id] += tmp;
                cur = a[j] - tmp * dif;

                if (cur < 0)
                {
                    ans[id] = -1;
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

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