제출 #391482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391482		ritul_kr_singh	Snowball (JOI21_ho_t2)	C++17	100 / 100	120 ms	16856 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, q; cin >> n >> q;
	int x[n]; for(int &i : x) cin >> i;
	int w[q]; for(int &i : w) cin >> i;

	int a[q], b[q];
	a[0] = max(w[0], 0LL);
	b[0] = min(w[0], 0LL);

	for(int i=1; i<q; ++i){
		w[i] += w[i-1];
		a[i] = max(a[i-1], w[i]);
		b[i] = min(b[i-1], w[i]);
	}

	for(int &i : b) i = -i;

	int l[n], r[n];
	fill(l, l+n, 0LL);
	fill(r, r+n, 0LL);

	for(int i=0; i+1<n; ++i){
		int diff = x[i+1] - x[i];
		if(a[0] + b[0] >= diff){
			r[i] = min(diff, a[0]);
			l[i+1] = min(diff, b[0]);
			continue;
		}
		int low = 0, high = q-1;
		while(low < high){
			int mid = (low + high) / 2;
			if(a[mid+1] + b[mid+1] < diff) low = mid+1;
			else high = mid;
		}
		int mx = low;
		r[i] = a[mx];
		l[i+1] = b[mx];
		++mx;
		if(mx < q){
			l[i+1] = min(diff - a[mx-1], b[mx]);
			r[i] = min(diff - b[mx-1], a[mx]);
		}
	}
	l[0] = b[q-1];
	r[n-1] = a[q-1];
	for(int i=0; i<n; ++i) cout << l[i] + r[i] nl;
}

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