Submission #1272761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272761		AbdullahIshfaq	Fish 3 (JOI24_fish3)	C++20	27 / 100	246 ms	78352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
void solve()
{
	ll n, d, q, l, r;
	cin >> n >> d;
	vector<ll> c(n + 1), req(n + 1), mn(n + 1), pre1(n + 1), pre2(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i];
	}
	for (int i = n - 1; i > 0; i--)
	{
		req[i] = max(0ll, (c[i] - c[i + 1] + d - 1 + req[i + 1] * d) / d);
	}
	priority_queue<pair<int, int>> pq;
	req[0] = -1;
	for (int i = n; i >= 0; i--)
	{
		pq.push({req[i], i});
		while (req[i] < pq.top().first)
		{
			mn[pq.top().second] = i;
			pq.pop();
		}
	}
	for (int i = 1; i <= n; i++)
	{
		pre1[i] = pre1[mn[i]] + req[i] * (i - mn[i]);
		pre2[i] = pre2[i - 1] + req[i];
	}
	vector<vector<ll>> bl(n + 1, vector<ll>(20, -1));
	for (int i = 0; i <= n; i++)
	{
		bl[i][0] = mn[i];
	}
	for (int j = 1; j < 20; j++)
	{
		for (int i = 0; i <= n; i++)
		{
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> l >> r;
		ll m = r;
		for (int i = 19; i >= 0; i--)
		{
			if (bl[m][i] >= l)
			{
				m = bl[m][i];
			}
		}
		if (c[l] < (req[l] - req[m]) * d)
		{
			cout << -1 << '\n';
		}
		else
		{
			cout << pre2[r] - pre2[l - 1] - (pre1[r] - pre1[m] + req[m] * (m - l + 1)) << '\n';
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for (int i = 1; i <= tests; i++)
		solve();
}

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