Submission #1176166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176166		Tsagana	Snowball (JOI21_ho_t2)	C++20	100 / 100	69 ms	9868 KiB

Main

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int X[200010];
int W[200010];
int L[200010];
int R[200010];
int ans[200010];

void solve () {
	int n, q;
	cin >> n >> q;
	
	for (int i = 1; i <= n; i++) cin >> X[i];
	
	int sum = 0;
	for (int i = 1; i <= q; i++) {
		cin >> W[i];
		sum += W[i];
		L[i] = min(L[i-1], sum);
		R[i] = max(R[i-1], sum);
	}

	ans[1] -= L[q];
	ans[n] += R[q];
	for (int i = 1; i < n; i++) {
		int l = 0, r = q, k = 0;
		while (l <= r) {
			int m = (l + r) / 2;
			if (R[m] - L[m] >= X[i+1] - X[i]) r = m - 1;
			else {l = m + 1; k = m;}
 		}
		ans[i] += R[k];
		ans[i+1] -= L[k];
		if (k == q) continue;
		if (W[k+1] > 0) ans[i] += (X[i+1] - X[i]) - (R[k] - L[k]);
		else ans[i+1] += (X[i+1] - X[i]) - (R[k] - L[k]);
	}
	for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}
signed main() {IOS solve(); return 0;}

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