Submission #703184

#	Time	Username	Problem	Language	Result	Execution time	Memory
703184		ld_minh4354	Snowball (JOI21_ho_t2)	C++17	100 / 100	250 ms	26244 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"



signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int n,m,i,x[200005],w[200005],l[200005],r[200005],ldist,rdist,l1,l2,r1,r2;
	set<pair<int,pair<int,int>>> s;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>x[i];
	for (i=1;i<m+1;i++) cin>>w[i];
	for (i=2;i<m+1;i++) w[i]+=w[i-1];
	
	ldist=rdist=0;
	s.insert({0,{0,0}});
	for (i=1;i<m+1;i++)
	{
		if (w[i]<0) ldist=max(ldist, -w[i]);
		else rdist=max(rdist, w[i]);
		
		s.insert({ldist + rdist, {ldist, rdist}});
	}
	
	l[1]=ldist;
	r[n]=rdist;
	
	// calculate r[i] and l[i+1]
	for (i=1;i<n;i++)
	if (x[i+1]-x[i]>=ldist+rdist)
	{
		r[i]=rdist;
		l[i+1]=ldist;
	}
	else
	{
		auto pt=s.lower_bound({x[i+1] - x[i], {0,0}});
		
		l2=(*pt).se.fi;
		r2=(*pt).se.se;
		
		pt--;
		
		l1=(*pt).se.fi;
		r1=(*pt).se.se;
		
		if (l2>l1)
		{
			r[i]=r1;
			l[i+1]=x[i+1]-x[i]-r[i];
		}
		else
		{
			l[i+1]=l1;
			r[i]=x[i+1]-x[i]-l[i+1];
		}
	}
	
//	for (i=1;i<n+1;i++) cout<<l[i]<<" ";
//	cout<<"\n";
//	for (i=1;i<n+1;i++) cout<<r[i]<<" ";
//	cout<<"\n";
	
	for (i=1;i<n+1;i++) cout<<l[i]+r[i]<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:20:73: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
   20 |  int n,m,i,x[200005],w[200005],l[200005],r[200005],ldist,rdist,l1,l2,r1,r2;
      |                                                                         ^~

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