Submission #1129096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129096		jj_master	Fish 3 (JOI24_fish3)	C++20	0 / 100	613 ms	78692 KiB

Main

// JOI 2024 (Fish 3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second
#define ins insert
#define eb emplace_back

void sol()
{
	int n, d;
	cin >> n >> d;
	vector<int> a(n + 1);
	for(int i=0;i<n;i++) cin >> a[i];
	vector<int> cur(n + 1), actreq(n + 1), req(n + 1), preq(n + 1);
	int ofs = 0;
	for(int i=1;i<=n;i++) {
		cur[i] = cur[i - 1] + ((d + (a[i] % d) - (cur[i-1] % d)) %d);
		req[i] = actreq[i] = (a[i] - cur[i]) / d;
		ofs = min(ofs, actreq[i]);
	} 
	ofs = - ofs;
	for(int i=1;i<=n;i++) req[i] += ofs;
	for(int i=1;i<=n;i++) preq[i] = req[i] + preq[i - 1];
	vector<vector<int>> li(n + 1, vector<int>(19));
	vector<vector<int>> lis(n + 1, vector<int>(19));
	{
	    stack<pair<int,int>> s;
		s.emplace(0,0);
		for(int i=1;i<=n;i++) {
			while(s.top().fi > req[i]) s.pop();
			li[i][0] = s.top().se;
			lis[i][0] = req[i] * (i - s.top().se);
			s.emplace(req[i], i);
		}	
		for(int j=1;j<=18;j++) {
			for(int i=1;i<=n;i++) {
				li[i][j] = li[li[i][j - 1]][j - 1];
				lis[i][j] = lis[li[i][j - 1]][j - 1] + lis[i][j - 1];
			}
		}
	}
	int q;
	cin >> q;
	for(int i=1;i<=q;i++) {
		int l ,r;
		cin >> l >> r;
		int ans = preq[r] - preq[l - 1];
		for(int j=18;j>=0;j--) {
			if(li[r][j] >= l){
				ans -= lis[r][j];
				r = li[r][j];
			}
		}
		ans -= req[r] * (r - l + 1);
		if(actreq[r] + cur[l] / d >= 0) cout << ans << '\n';
		else cout << "-1" << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	sol();
	return 0;
}

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