Submission #1286763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286763		Jawad_Akbar_JJ	Snowball (JOI21_ho_t2)	C++20	100 / 100	411 ms	11584 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
const int N = 1<<18;
int a[N], pre[N], suf[N], Min[N], inf = 3e17;

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, q;
	cin>>n>>q;

	vector<pair<int,int>> vec = {{0, 0}};
	for (int i=1;i<=n;i++)
		cin>>a[i];

	for (int i=1;i<=q;i++){
		cin>>pre[i];
		pre[i] += pre[i-1];
		Min[i] = min(Min[i-1], pre[i]);

		vec.push_back({pre[i], i});
	}

	sort(begin(vec), end(vec));

	suf[q + 1] = q + 1, a[n + 1] = inf;
	for (int i=q;i>=0;i--)
		suf[i] = min(suf[i+1], vec[i].second);

	int lft = -inf;

	for (int i=1;i<=n;i++){
		lft = max(lft, min(a[i], a[i] + Min[q]));
		
		int l = 0, r = min(vec.back().first + 1, a[i + 1] - a[i] + 1);

		while (l + 1 < r){
			int mid = (l + r) / 2;
			int u = suf[upper_bound(begin(vec), end(vec), make_pair(mid, 0LL)) - begin(vec)];

			if (u == q + 1 or -Min[u] > a[i + 1] - a[i] - mid)
				r = mid;
			else
				l = mid;
		}

		cout<<a[i] + l - lft<<'\n';
		lft = a[i] + l;
	}
}

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