제출 #391485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391485		ritul_kr_singh	Snowball (JOI21_ho_t2)	C++17	100 / 100	120 ms	11348 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 mx = 0, 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;
		}
		for(int y=1<<18; y; y/=2)
			if(mx+y < q and a[mx+y] + b[mx+y] < diff) mx += y;
		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