Submission #371256

#	Time	Username	Problem	Language	Result	Execution time	Memory
371256		cheissmart	Snowball (JOI21_ho_t2)	C++14	100 / 100	130 ms	11500 KiB

Main

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;


void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h);
	if(sizeof...(t)) cerr << ", ";
	DBG(t...);
}
#define debug(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 200005;

ll x[N], w[N], ans[N], len[N], L[N], R[N];

signed main()
{
	IO_OP;
	
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
		cin >> x[i];
	ll cur = 0, l = 0, r = 0;
	for(int i = 0; i < q; i++) {
		cin >> w[i];
		cur += w[i];
		r = max(r, cur);
		l = min(l, cur);
		len[i] = r - l;
		L[i] = l, R[i] = r;
	}
	ans[0] += -l, ans[n - 1] += r;
	for(int i = 0; i < n - 1; i++) {
		ll t = x[i + 1] - x[i];
		if(r - l <= t) {
			ans[i] += r, ans[i + 1] -= l;
		}
		else {
			int pos = upper_bound(len, len + q, t) - len;
			assert(pos < q);
			if(w[pos] > 0) { // r increase
				ans[i + 1] -= L[pos];
				ans[i] += t + L[pos];
			} else {
				ans[i] += R[pos];
				ans[i + 1] += t - R[pos];
			}
		}
	}
	for(int i = 0; i < n; i++)
		cout << ans[i] << '\n';

}

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