Submission #1129099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129099		jj_master	Fish 3 (JOI24_fish3)	C++20	0 / 100	721 ms	79228 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> arr(n+1);
	for(int i=1;i<=n;i++)cin>>arr[i];
	vector<int> curr(n+1), actreq(n+1), req(n+1), preq(n+1);
	int offset = 0;
	for(int i=1;i<=n;i++) {
		curr[i] = curr[i-1]+((d+(arr[i]%d)-(curr[i-1]%d))%d);
		req[i] = actreq[i] = (arr[i]-curr[i])/d;	
		offset = min(offset,actreq[i]);
	}
	offset = -offset;
	for(int i=1;i<=n;i++) req[i]+=offset;
	for(int i=1;i<=n;i++) preq[i]=req[i]+preq[i-1];
	vector<vector<int>> lift(n+1,vector<int>(19));
	vector<vector<int>> liftsum(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();
			lift[i][0] = s.top().se;
			liftsum[i][0] = req[i]*(i-s.top().se);
			s.emplace(req[i],i);
		}
		for(int bit=1;bit<=18;bit++) {
			for(int i=1;i<=n;i++) {
				lift[i][bit] = lift[lift[i][bit-1]][bit-1];
				liftsum[i][bit] = liftsum[lift[i][bit-1]][bit-1]+liftsum[i][bit-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 bit=18;bit>=0;bit--) {
			if(lift[r][bit]>=l){
				ans-=liftsum[r][bit];
				r = lift[r][bit];
			}
		}
		ans-=req[r]*(r-l+1);
		if(actreq[r]+curr[l]/d>=0)cout<<ans<<'\n';
		else cout << "-1\n";
	}
}

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

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