Submission #1110175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110175		vjudge1	Fish 3 (JOI24_fish3)	C++17	0 / 100	13 ms	6480 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
using namespace std;
ll n,d,q,a[300005],r[300005],b[300005],bu[300005];
bool sub2=true;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".INP","r",stdin);
//	freopen(".OUT","w",stdout);
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		r[i]=a[i]%d;
	}
	cin>>q;
	if(q<=3000)
	{
		while(q--)
		{
			bool kt=true;
			int l,rr;
			ll mx=1e9;
			cin>>l>>rr;
			b[l]=0;
			bu[l]=(a[l]-d*b[l]-r[l])/d;
			if(bu[l]<0)
			{
				cout<<-1<<endl;
				continue;
			}
			mx=bu[l];
			for(int i=l+1;i<=rr;i++)
			{
				if(r[i]<r[i-1]) b[i]=b[i-1]+1;
				else b[i]=b[i-1];
				
				bu[i]=(a[i]-d*b[i]-r[i])/d;
				if(bu[i]<0)
				{
					kt=false;
					break;
				}
				mx=min(mx,bu[i]);
			}
			
			if(!kt)
			{
				cout<<-1<<endl;
				continue;
			}
			
			int ans=0;
			for(int i=l;i<=rr;i++)
			{
				ans+=(a[i]-(b[i]+mx)*d-r[i])/d;
			}
			cout<<ans<<endl;
			
		}
		
		return 0;
	}
	return 0;
}

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