Submission #528114

#	Time	Username	Problem	Language	Result	Execution time	Memory
528114		Jasiekstrz	Snowball (JOI21_ho_t2)	C++17	100 / 100	127 ms	13768 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const long long INF=1e18L+7;
long long x[N+10];
long long w[N+10];
pair<long long,long long> seg[N+10];
int bs(long long d,int q)
{
	int bg=0,en=q;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		if(seg[mid].se-seg[mid].fi<=d)
			bg=mid;
		else
			en=mid-1;
	}
	return bg;
}
long long solver(long long d,int q)
{
	int it=bs(d,q);
	if(it==q)
		return -seg[it].fi;
	if(w[it+1]<0)
		return d-seg[it].se;
	return -seg[it].fi;
}
long long solvel(long long d,int q)
{
	int it=bs(d,q);
	if(it==q)
		return seg[it].se;
	if(w[it+1]>0)
		return d+seg[it].fi;
	return seg[it].se;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	seg[0]={0,0};
	long long pos=0;
	for(int i=1;i<=q;i++)
	{
		cin>>w[i];
		pos+=w[i];
		seg[i].fi=min(seg[i-1].fi,pos);
		seg[i].se=max(seg[i-1].se,pos);
	}
	x[0]=-INF;
	x[n+1]=INF;
	for(int i=1;i<=n;i++)
		cout<<solver(x[i]-x[i-1],q)+solvel(x[i+1]-x[i],q)<<"\n";
	return 0;
}

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