Submission #372514

#	Time	Username	Problem	Language	Result	Execution time	Memory
372514		Kevin_Zhang_TW	Snowball (JOI21_ho_t2)	C++17	100 / 100	165 ms	11628 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;

ll mx[MAX_N], mn[MAX_N], sum[MAX_N], delta[MAX_N];

const ll inf = 1ll << 60;

int n, q;
ll X[MAX_N];

ll res[MAX_N];

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	for (int i = 1;i <= n;++i) 
		cin >> X[i];

	for (int i = 1;i <= q;++i)
		cin >> delta[i];

	{
		ll diff = 0;
		for (int i = 1;i <= q;++i) {
			diff += delta[i];
			mx[i] = max(mx[i-1], diff);
			mn[i] = min(mn[i-1], diff);
			sum[i] = mx[i] - mn[i];
		}
	}

	DE(mn[q], mx[q]);

	{

		X[0] = X[1] - inf;
		X[n+1] = X[n] + inf;

		for (int i = 1;i <= n + 1;++i) {
			ll dis = X[i] - X[i-1];

			int l = 0, r = q, mid;
			while (l < r) {
				mid = l + r >> 1;
				if (sum[mid + 1] > dis)
					r = mid;
				else l = mid + 1;
			}
			ll tol = mn[l], tor = mx[l], lft = dis - (tor - tol);

			res[i-1] += abs(tor);
			res[i] += abs(tol);

			if (l == q) continue;

			if (delta[l + 1] <= 0) 
				res[i] += lft;
			else
				res[i-1] += lft;

		}
	}
	for (int i = 1;i <= n;++i)
		cout << res[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Main.cpp:48:2: note: in expansion of macro 'DE'
   48 |  DE(mn[q], mx[q]);
      |  ^~
Main.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     mid = l + r >> 1;
      |           ~~^~~

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