Submission #469320

#	Time	Username	Problem	Language	Result	Execution time	Memory
469320		jason7777	Snowball (JOI21_ho_t2)	C++14	100 / 100	137 ms	15300 KiB

Main

#pragma GCC optmize ("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define spIO ios::sync_with_stdio(false);cin.tie(0)
#define mem(x,va) memset(x,va,sizeof(x))
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
inline ll inv(ll x, ll MOD = mod)
{
	ll power = MOD - 2, ret = 1;
	while (power)
	{
		if (power & 1)
			(ret *= x) %= MOD;
		power >>= 1;
		(x *= x) %= MOD;
	}
	return ret;
}
inline ll gcd(ll x, ll y)
{
	if (y == 0) return x;
	return gcd(y, x % y);
}
ll pow2(ll target, ll p)
{
	ll ret = 1;
	while (p)
	{
		if (p & 1)
			(ret *= target) %= mod;
		p >>= 1;
		(target *= target) %= mod;
	}
	return ret;
}

ll n, q;
ll x[200000 + 5], w[200000 + 5], r[200000 + 5], l[200000 + 5], ans[200000 + 5];

ll bs(ll tar)
{
	int left = 0, right = q + 1, mid;
	while (left != right)
	{
		mid = (left + right) / 2;
		if (r[mid] + l[mid] <= tar)
			left = mid + 1;
		else
			right = mid;
	}
	return left;
}

int main()
{
	spIO;
	cin >> n >> q;
	for1(i, n) cin >> x[i];
	for1(i, q) cin >> w[i];
	ll ip = 0;
	l[0] = r[0] = 0;
	for1(i, q)
	{
		ip += w[i];
		r[i] = max(r[i - 1], ip);
		l[i] = max(l[i - 1], -ip);
	}

	ans[1] += l[q];
	for (int i = 2; i <= n; i++)
	{
		if (l[q] + r[q] <= x[i] - x[i - 1])
		{
			ans[i - 1] += r[q];
			ans[i] += l[q];
		}
		else
		{
			ll t = bs(x[i] - x[i - 1]);
			if (r[t] - r[t - 1] > 0)
			{
				ans[i - 1] += x[i] - x[i - 1] - l[t];
				ans[i] += l[t];
			}
			else
			{
				ans[i] += x[i] - x[i - 1] - r[t];
				ans[i - 1] += r[t];
			}
		}
		//cout << i - 1 << ' ' << i << ' ' << ans[i - 1] << ' ' << ans[i] << '\n';
	}
	ans[n] += r[q];
	for1(i, n) cout << ans[i] << ' '; cout << '\n';
}

/*

*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    1 | #pragma GCC optmize ("O3,unroll-loops")
      | 
Main.cpp: In function 'int main()':
Main.cpp:7:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    7 | #define for1(i,n) for(int i=1;i<=n;i++)
      |                   ^~~
Main.cpp:98:2: note: in expansion of macro 'for1'
   98 |  for1(i, n) cout << ans[i] << ' '; cout << '\n';
      |  ^~~~
Main.cpp:98:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |  for1(i, n) cout << ans[i] << ' '; cout << '\n';
      |                                    ^~~~

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