Submission #1225700

#TimeUsernameProblemLanguageResultExecution timeMemory
1225700boclobanchatSnowball (JOI21_ho_t2)C++20
0 / 100
1 ms328 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
long long A[MAXN],L[MAXN],R[MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>A[i];
	long long pos=0;
	for(int i=1;i<=q;i++)
	{
		long long res;
		cin>>res;
		pos+=res,L[i]=min(L[i-1],pos),R[i]=max(R[i-1],pos);
	}
	for(int i=1;i<=n;i++)
	{
		long long ans=0;
		if(i<n)
		{
			int l=1,r=q,pos=q;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(A[i]+R[mid]<=A[i+1]+L[mid]) l=mid+1;
				else r=mid-1,pos=mid;
			}
			if(L[pos]<L[pos-1]) ans+=R[pos];
			else ans+=A[i+1]+L[pos]-A[i];
		}
		else ans+=R[q];
		if(i>1)
		{
			int l=1,r=q,pos=q;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(A[i]+L[mid]>=A[i-1]+R[mid]) l=mid+1;
				else r=mid-1,pos=mid;
			}
			if(R[pos]>R[pos-1]) ans-=L[pos];
			else ans+=A[i]-A[i-1]-R[pos];
		}
		else ans-=L[q];
		cout<<ans<<"\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...