Submission #953835

#	Time	Username	Problem	Language	Result	Execution time	Memory
953835		manishjha91	Snowball (JOI21_ho_t2)	C++17	100 / 100	126 ms	28612 KiB

Main

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

using ll = long long;
using ull = unsigned long long;
using lld = long double;

// #ifndef ONLINE_JUDGE
// #include "D:\cpp_codes\debugalgo.h"
// #else
// #define debug(x)
// #endif

const ll inf = 1e18;

void solve()
{
	int n,q;
	cin>>n>>q;
	
	vector<ll> a(n);
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	
	vector<ll> b(q);
	
	for(int i=0; i<q; i++)
	{
		cin>>b[i];
		if(i) b[i]+=b[i-1];
	}
	
	// debug(b);
	
	vector<ll> mx(q,-inf),mn(q,inf);
	mx[0] = max(0LL,b[0]);
	mn[0] = min(0LL,b[0]);
	for(int i=1; i<q; i++)
	{
		mx[i] = max({0LL,mx[i-1],b[i]});
		mn[i] = min({0LL,mn[i-1],b[i]});
	}
	
	// debug(mn);
	// debug(mx);
	
	vector<pair<ll,pair<ll,ll>>> vright,vleft;
	vright.push_back({mx[0],{mx[0],0LL}});

	for(int i=1; i<q; i++)
	{
		vright.push_back({mx[i]-mn[i-1],{mx[i],mn[i-1]}});
	}
	
	// debug(vright);
	
	vleft.push_back({-mn[0],{-mn[0],0LL}});
	for(int i=1; i<q; i++)
	{
		vleft.push_back({mx[i-1]-mn[i],{-mn[i],mx[i-1]}});
	}
	
	// debug(vleft);
	
	vector<ll> ans(n);
	
	for(int i=0; i<n; i++)
	{
		ll left=-inf,right=-inf;
		
		if(i==0)
		{
			left = -mn.back();
		}
		else
		{
			ll delta = a[i]-a[i-1];
			
			auto itn = upper_bound(vleft.begin(),vleft.end(),make_pair(delta,make_pair(-1LL,-1LL)));
			
			//intersecting
			if(itn!=vleft.end())
			{
				left = max(left,delta - (*itn).second.second);
			}
			// no non-intersection
			if(itn!=vleft.begin())
			{
				itn--;
				left = max(left,(*itn).second.first);
			}
			
			
		}
		if(i==n-1)
		{
			right = mx.back();
		}
		else
		{
			ll delta = a[i+1]-a[i];
			
			auto it = upper_bound(vright.begin(),vright.end(),make_pair(delta,make_pair(-1LL,-1LL)));
			
			//intersecting
			if(it!=vright.end())
			{
				right = max(right, delta + (*it).second.second);
			}
			
			//non-intersecting
			
			if(it!=vright.begin())
			{
				it--;
				right = max(right, (*it).second.first);
				
			}
		}
		
		ans[i] = left + right;
		
		cout<<ans[i]<<"\n";
	}
	
	
	
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

// #ifndef ONLINE_JUDGE
// 	freopen("error.txt", "w", stderr);
// #endif

	int tt = 1;
	// cin >> tt;
	while (tt--)
	{
		solve();
	}
}

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