Submission #371265

#	Time	Username	Problem	Language	Result	Execution time	Memory
371265		arnold518	Snowball (JOI21_ho_t2)	C++14	100 / 100	136 ms	11500 KiB

Main

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, Q;
ll A[MAXN+10], B[MAXN+10];
ll C[MAXN+10], D[MAXN+10], E[MAXN+10];
ll ans[MAXN+10];

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
	for(int i=1; i<=Q; i++) scanf("%lld", &B[i]);

	ll now=0;
	for(int i=1; i<=Q; i++)
	{
		now+=B[i];
		E[i]=now;
		C[i]=min(C[i-1], now);
		D[i]=max(D[i-1], now);
	}

	for(int i=1; i<N; i++)
	{
		ll d=A[i+1]-A[i];


		int lo=0, hi=Q+1;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(D[mid]-C[mid]<=d) lo=mid;
			else hi=mid;
		}
		if(lo==Q)
		{
			ans[i]+=D[Q];
			ans[i+1]-=C[Q];
		}
		else
		{
			if(C[lo]==C[hi])
			{
				ans[i+1]-=C[lo];
				ans[i]+=d+C[lo];
			}
			else
			{
				ans[i]+=D[lo];
				ans[i+1]+=d-D[lo];
			}
		}
	}
	ans[1]-=C[Q];
	ans[N]+=D[Q];
	for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    int mid=lo+hi>>1;
      |            ~~^~~
Main.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:18:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
Main.cpp:19:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  for(int i=1; i<=Q; i++) scanf("%lld", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~

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