Submission #1161404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161404		Nurislam	Snowball (JOI21_ho_t2)	C++20	100 / 100	132 ms	11800 KiB

Main

#include <bits/stdc++.h>

using namespace std;


#define int long long
#define pb push_back

int inf = -1e18;

void solve(){
	int n, q;
	cin >> n >> q;
	vector<int> l(n), r(n), a(n);
	for(int i = 0; i < n; i ++ ){
		cin >> a[i];
		r[i] = l[i] = a[i];
	}
	
	vector<int> pr{0}, mn{0}, mx{0};
	for(int i = 0; i < q; i ++ ) {
		int x; cin >> x;
		pr.push_back(pr[i] + x);
		mn.push_back(min(mn[i], pr[i+1]));
		mx.push_back(max(mx[i], pr[i+1]));
	};
	
	l[0] = a[0] + mn[q];
	for(int i = 1; i < n; i ++ ) {
		int li = 0, ri = q;
		while(li < ri){
			int m = (li + ri) >> 1;
			if(a[i-1] + mx[m] < a[i] + mn[m]) li = m + 1;
			else ri = m;
		};
		
		l[i] = max(a[i] + mn[li], a[i-1] + mx[li-1]);
		r[i-1] = min(a[i-1] + mx[li], a[i] + mn[li-1]);
		//cout << i << ' ' << li << '\n';
	}
	
	r[n-1] = a[n-1] + mx[q];
	
	for(int i = 0; i < n; i ++ ) {
		cout << r[i] - l[i] << '\n';
	};
	
};

signed main(){
	ios_base::sync_with_stdio();
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

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