제출 #403614

#제출 시각아이디문제언어결과실행 시간메모리
403614Drew_Snowball (JOI21_ho_t2)C++17
100 / 100
134 ms15460 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
#define ll long long
#define ii pair<int, int>
#define pl pair<ll, ll>
#define f1 first
#define s2 second

const int MAX = 2e5 + 7;

int n, m;
ll X[MAX], res[MAX], kaze[MAX];

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> X[i];
	for (int i = 1; i <= m; ++i)
		cin >> kaze[i], kaze[i] += kaze[i-1];

	vector<pl> v;
	for (int i = 1; i+1 <= n; ++i)
		v.pb({X[i+1] - X[i], i});

	sort(v.begin(), v.end());

	int idx = 0;
	ll l = 0, r = 0; //l: west to east, r: east to west
	for (int i = 1; i <= m; ++i)
	{
		if (kaze[i] < 0) //add something to r
		{
			while (idx < n-1 && l + max(r, -kaze[i]) >= v[idx].f1)
			{
				res[v[idx].s2] += l;
				res[v[idx].s2 + 1] += v[idx].f1 - l;
				idx++;
			}
			r = max(r, -kaze[i]);
		}
		else
		{
			while (idx < n-1 && r + max(l, kaze[i]) >= v[idx].f1)
			{
				res[v[idx].s2] += v[idx].f1 - r;
				res[v[idx].s2 + 1] += r;
				idx++;
			}
			l = max(l, kaze[i]);
		}
	}
	while (idx < n-1)
	{
		res[v[idx].s2] += l;
		res[v[idx].s2 + 1] += r;
		idx++;
	}

	res[1] += r, res[n] += l;
	for (int i = 1; i <= n; ++i)
		cout << res[i] << '\n';

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...