Submission #1284880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284880		MuhammadSaram	Fish 3 (JOI24_fish3)	C++20	44 / 100	1447 ms	37360 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'
#define all(v) v.begin(), v.end()

const int M = 3e5 + 1;

int seg[M*2], lz[M*2];

void push(int v,int s,int e)
{
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	seg[lc]=lz[v]*(mid-s), seg[rc]=lz[v]*(e-mid);
	lz[lc]=lz[rc]=lz[v];
	lz[v]=-1;
}

void modify(int l,int r,int x,int v=0,int s=0,int e=M)
{
	if (l>=e or r<=s) return;
	if (l<=s && e<=r)
	{
		seg[v]=x*(e-s), lz[v]=x;
		return;
	}
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	if (~lz[v]) push(v,s,e);
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=seg[lc]+seg[rc];
}

int get(int l,int r,int v=0,int s=0,int e=M)
{
	if (l>=e or r<=s) return 0;
	if (l<=s && e<=r) return seg[v];
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	if (~lz[v]) push(v,s,e);
	return get(l,r,lc,s,mid)+get(l,r,rc,mid,e);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	for (int i=0;i<M*2;i++) lz[i]=-1;
	
	int n,d;
	cin>>n>>d;
	int a[n];
	for (int i=0;i<n;i++)
		cin>>a[i];
	if (n<=3000)
	{
		int q;
		cin>>q;
		int val[n];
		while (q--)
		{
			int l,r;
			cin>>l>>r;l--;
			bool pos=1;
			int cnt=0;
			for (int i=l;i+1<r && pos;i++)
			{
				val[i]=a[i]/d-cnt;
				if (a[i+1]%d<a[i]%d) cnt++;
			}
			val[r-1]=a[r-1]/d-cnt;
			for (int i=l;i<r;i++)
				if (val[i]<0) pos=0;
			if (!pos)
			{
				cout<<-1<<endl;
				continue;
			}
			int ans=0,mn=val[r-1];
			for (int i=r-1;i>=l;i--)
				mn=min(mn,val[i]), ans+=val[i]-mn;
			cout<<ans<<endl;
		}
	}
	else if(d==1)
	{
		int q;
		cin>>q;
		int ans[q], pre[n+1]={};
		vector<pair<int,int>> v[n];
		for (int i=0;i<q;i++)
		{
			int l,r;
			cin>>l>>r;l--,r--;
			v[r].push_back({l,i});
		}
		stack<pair<int,int>> st;
		st.push({-1,-1});
		for (int i=0;i<n;i++)
		{
			pre[i+1]=pre[i]+a[i];
			while (!st.empty() && st.top().first>=a[i])
				st.pop();
			modify(st.top().second+1, i+1, a[i]);
			for (auto [l,id]:v[i])
				ans[id]=pre[i+1]-pre[l]-get(l,i+1);
			st.push({a[i],i});
		}
		for (int i=0;i<q;i++)
			cout<<ans[i]<<endl;
	}
	else
	{
		int pre[n+1]={};
		vector<int> v;
		for (int i=0;i<n;i++)
		{
			pre[i+1]=pre[i]+a[i];
			if (!a[i]) v.push_back(i);
		}
		int q;
		cin>>q;
		while (q--)
		{
			int l,r;
			cin>>l>>r;l--;
			int x=lower_bound(all(v),r)-begin(v),ans=0;
			if (x && pre[v[x-1]]>pre[l])
				ans=(d>1?-1:pre[v[x-1]]-pre[l]);
			cout<<ans<<endl;
		}
	}
	
	return 0;
}

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