Submission #880561

#	Time	Username	Problem	Language	Result	Execution time	Memory
880561		OAleksa	Snowball (JOI21_ho_t2)	C++14	100 / 100	89 ms	15740 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
   int tt = 1;
  	//cin >> tt;
   while (tt--) {
   	int n, q;
   	cin >> n >> q;
   	vector<int> a(n), w(q);
   	for (int i = 0;i < n;i++)
   		cin >> a[i];
   	int l = 0, r = 0, s = 0;
   	vector<pair<int, int>> seg;
   	seg.push_back({0, 0});
   	for (int i = 0;i < q;i++)
   		cin >> w[i];
   	for (int i = 0;i < q;i++) {
   		s += w[i];
   		l = min(l, s);
   		r = max(r, s);
   		seg.push_back({abs(l), r});
   	}
   	vector<int> ans(n);
   	for (int i = 0;i < n - 1;i++) {
			int l = 1, r = q, x = 0;
			int d = a[i + 1] - a[i];
			while (l <= r) {
				int mid = (l + r) / 2;
				int c = seg[mid].f + seg[mid].s;
				if (c <= d) {
					x = mid;
					l = mid + 1;
				}
				else
					r = mid - 1;
			}
			if (x == q) {
				ans[i] += seg[x].s;
				ans[i + 1] += seg[x].f;
			}
			else {
				int u;
				if (seg[x + 1].f != seg[x].f) {
					u = min(seg[x + 1].f, d - seg[x].s);
					ans[i + 1] += u;
					ans[i] += d - u;
				}
				else {
					u = min(seg[x + 1].s, d - seg[x].f);
					ans[i] += u;
					ans[i + 1] += d - u;
				}
			}
   	}
   	ans[0] += abs(l);
   	ans[n - 1] += r;
   	for (int i = 0;i < n;i++)
   		cout << ans[i] << '\n';
	}
	return 0;
}

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