Submission #1225704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225704		boclobanchat	Snowball (JOI21_ho_t2)	C++20	100 / 100	90 ms	6728 KiB

Main

#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+1;
			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(pos==q+1) ans+=R[q];
			else 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+1;
			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(pos==q+1) ans-=L[q];
			else 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";
	}
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67