Submission #1086014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086014		rsinventor	Snowball (JOI21_ho_t2)	C++17	100 / 100	115 ms	13896 KiB

Main

/*
	Keep track of prefix maximum and minimum as these things tell us the highest and the lowest points we reached so far with the snowballs
	
	For each pair of two adjacent snowballs, we should binary search the point x at which maxq[x] + abs(minq[x]) >= v[i+1] - v[i] and then add accordingly
to each end based on where the last update came from

	We should deal separately with the two extremes too
	
*/

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, q;
	cin >> n >> q;
	
	vector<long long> v(n+1);
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	
	vector<long long> minq(q+1), maxq(q+1);
	long long sum = 0;

	for(int i = 1; i <= q; i++)
	{
		long long x;
		cin >> x;
		sum += x;
		minq[i] = min(minq[i-1], sum);
		maxq[i] = max(maxq[i-1], sum);
	}
	
	vector<long long> ans(n+1);
	for(int i = 1; i < n; i++)
	{
		int st = 1;
		int dr = q;
		int poz = 0;
		while(st <= dr)
		{
			int mid = (st + dr) / 2;
			if(abs(minq[mid]) + abs(maxq[mid]) < v[i+1] - v[i])
			{
				poz = mid;
				st = mid + 1;
			}
			else
				dr = mid - 1;
		}
		
		ans[i] += maxq[poz];
		ans[i+1] += abs(minq[poz]);
		
		if(poz != q && maxq[poz+1] > maxq[poz])
			ans[i] += (v[i+1] - v[i]) - (abs(minq[poz]) + abs(maxq[poz]));
		
		if(poz != q && minq[poz+1] < minq[poz])
			ans[i+1] += (v[i+1] - v[i]) - (abs(minq[poz]) + abs(maxq[poz]));
	}
	
	ans[1] += abs(minq[q]);
	ans[n] += abs(maxq[q]);
	
	for(int i = 1; i <= n; i++)
		cout << ans[i] << '\n';
}

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