Submission #377677

#	Time	Username	Problem	Language	Result	Execution time	Memory
377677		Lawliet	Snowball (JOI21_ho_t2)	C++17	0 / 100	1 ms	364 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 200010;
const lli cte = 1000000000010;

int n, k;

lli x[MAXN];
lli power[MAXN], ans[MAXN];
lli minDiff[MAXN], maxDiff[MAXN];

bool test(int i, lli curX)
{
	if( curX < x[i] - minDiff[k] ) return false;
	if( x[i - 1] + maxDiff[k] < curX + 1 ) return true;

	int tRight = lower_bound( minDiff , minDiff + k + 1 , x[i] - curX ) - minDiff;
	int tLeft = lower_bound( maxDiff , maxDiff + k + 1 , curX + 1 - x[i - 1] ) - maxDiff;

	return ( tRight < tLeft );
}

lli bs(int i)
{
	lli l = x[i - 1], r = x[i] - 1;

	if( !test( i , r ) )
		return 0;

	while( l < r )
	{
		lli m = ( l + r )/2;

		if( test( i , m ) ) r = m;
		else l = m + 1;
	}

	return x[i] - r;
}

void solveTestCase(int testCase)
{
	scanf("%d %d",&n,&k);

	for(int i = 1 ; i <= n ; i++)
		scanf("%lld",&x[i]);

	for(int i = 1 ; i <= k ; i++)
		scanf("%lld",&power[i]);

	for(int t = 0 ; t < 2 ; t++)
	{
		lli curSum = 0;

		for(int i = 1 ; i <= n ; i++)
			x[i] += cte;

		for(int i = 1 ; i <= n ; i++)
		{
			curSum += power[i];

			maxDiff[i] = max( maxDiff[i - 1] , curSum );
			minDiff[i] = max( minDiff[i - 1] , -curSum );
		}

		for(int i = 1 ; i <= n ; i++)
		{
			int ind = i;
			if( t == 1 ) ind = n - i + 1;

			if( i == 1 ) ans[ind] += minDiff[k];
			else ans[ind] += bs( i );
		}

		for(int i = 1 ; i <= n ; i++)
			power[i] = -power[i], x[i] = cte - x[i];

		reverse( x + 1 , x + n + 1 );
	}

	for(int i = 1 ; i <= n ; i++)
		printf("%lld\n",ans[i]);
}

int main()
{
	int qtdTestCases = 1;
	// scanf("%d",&qtdTestCases);

	for(int testCase = 1 ; testCase <= qtdTestCases ; testCase++)
		solveTestCase( testCase );
}

Compilation message (stderr)

Main.cpp: In function 'void solveTestCase(int)':
Main.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d %d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
Main.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf("%lld",&x[i]);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%lld",&power[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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