Submission #1125412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125412		Kel_Mahmut	Snowball (JOI21_ho_t2)	C++20	100 / 100	74 ms	11452 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, Q;
	cin >> n >> Q;
	vector<ll> x(n);
	for(int i = 0; i < n; i++) cin >> x[i];
	vector<ll> W(Q);
	for(int i = 0; i < Q; i++) cin >> W[i];

	auto sign = [&](ll a){
		if(a < 0) return -1;
		if(a > 0) return 1;
		return 0;
	};

	vector<ll> pref(Q + 1);
	for(int i = 1; i <= Q; i++){
		pref[i] = pref[i - 1] + W[i - 1];
	}

	ll posmax = 0, posmin = 0;
	vector<ll> w = {0};
	int lst = -2;
	for(int i = 0; i <= Q; i++){
		if(sign(pref[i]) == 1 && pref[i] > posmax){
			posmax = pref[i];
			if(lst == 1)
				w.back() = pref[i];
			else
				w.pb(pref[i]);
			lst = 1;
		}
		if(sign(pref[i]) == -1 && abs(pref[i]) > abs(posmin)){
			posmin = pref[i];
			if(lst == -1)
				w.back() = pref[i];
			else
				w.pb(pref[i]);
			lst = -1;
		}
	}

	int q = w.size();
	vector<ll> dif(q - 1);
	for(int i = 0; i < q - 1; i++){
		dif[i] = abs(w[i]) + abs(w[i + 1]);
	}

	vector<ll> ans(n);
	ans[0] += abs(posmin);
	ans[n - 1] += posmax;
	for(int i = 0; i < n - 1; i++){ // i ve i + 1 arasi
		ll fark = x[i + 1] - x[i];
		int ind = lower_bound(all(dif), fark) - dif.begin();
		if(ind == (int) dif.size()){
			ans[i] += posmax;
			ans[i + 1] += abs(posmin);
			continue;
		}

		ll lim = w[ind];
		if(lim == 0){
			assert(ind + 1 < (int) w.size());
			if(w[ind + 1] > 0)
				ans[i] += fark;
			else
				ans[i + 1] += fark;
		}
		else if(lim > 0){
			ans[i] += lim;
			ans[i + 1] += fark - lim;
		}
		else{
			ans[i + 1] += abs(lim);
			ans[i] += fark - abs(lim);
		}
	}

	for(int i = 0; i < n; i++) cout << ans[i] << endl;
}

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