Submission #1096872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096872		I_am_Polish_Girl	Fish 3 (JOI24_fish3)	C++14	9 / 100	2097 ms	7760 KiB

Main

//#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;

int log_ = 11;
int inf = 4000000007000000007;

long long mod = 1000000007;

int p = 499;

int NADIYA = 39;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n , d;
	cin >> n >> d;

	vector <int> a(n);

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

	int q;
	cin >> q;

	for (int i = 0; i < q; i++)
	{
		int l, r;
		cin >> l >> r;

		l--;
		r--;

		int mx = a[r];

		int ans = 0;

		for (int j = r - 1; j >= l; j--)
		{
			if (mx > a[j])
			{
				mx = a[j];
			}
			else
			{
				int s = (a[j] - mx);

				int col = s / d + ((s % d) > 0);

				ans += col;

				mx = a[j] - col * d;
			}
		}

		if (mx < 0)
			cout << -1 << "\n";
		else
			cout << ans << "\n";
	}
	
}

/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/

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