제출 #403614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403614		Drew_	Snowball (JOI21_ho_t2)	C++17	100 / 100	134 ms	15460 KiB

Main

#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;
}

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