Submission #1036270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036270		Unforgettablepl	Fish 3 (JOI24_fish3)	C++17	100 / 100	728 ms	133208 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	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);
	vector<int> actreq(n+1);
	vector<int> req(n+1);
	vector<int> 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().first>req[i])s.pop();
			lift[i][0] = s.top().second;
			liftsum[i][0] = req[i]*(i-s.top().second);
			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";
	}
}

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