Submission #1204854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204854		namhh	Snowball (JOI21_ho_t2)	C++20	100 / 100	62 ms	11568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+1;
ll n,q,a[N],ans[N];
vector<ll>megu,aquaa,aqua;
vector<ll>cc;
vector<ll>dm;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	while(q--){
		ll x;
		cin >> x;
		if(x == 0) continue;
		if(!megu.size()) megu.push_back(x);
		else megu.push_back(megu.back()+x);
	}
	ll curd = 0;
	ll curam = 0;
	for(ll it: megu){
		if(it > 0){
			if(it > curd){
				aquaa.push_back(it);
				curd = it;
			}
		}
		else{
			if(llabs(it) > curam){
				aquaa.push_back(it);
				curam = llabs(it);
			}
		}
	}
	if(aquaa.size() > 1) for(int i = 0; i < (int)aquaa.size()-1; i++){
		if((aquaa[i] > 0 && aquaa[i+1] < 0) || (aquaa[i+1] > 0 && aquaa[i] < 0)) aqua.push_back(aquaa[i]);
	}
	if(!aquaa.empty()) aqua.push_back(aquaa.back());
	if(aqua.size() > 1)for(int i = 0; i < (int)aqua.size()-1; i++) dm.push_back(llabs(aqua[i])+llabs(aqua[i+1]));
	sort(dm.begin(),dm.end());
	//for(auto it: dm) cout << it << " ";
	//cout << "\n";
	for(int i = 1; i <= n-1; i++){
		if(!aqua.size()) continue;
		ll x = a[i+1]-a[i];
		int p = upper_bound(dm.begin(),dm.end(),x)-dm.begin()-1;
		if(p == int(dm.size())-1 && p != -1){
			if(aqua[p] > 0){
				ans[i] += aqua[p];
				ans[i+1] += llabs(aqua[p+1]);
			}
			else{
				ans[i] += aqua[p+1];
				ans[i+1] += llabs(aqua[p]);
			}
		}
		else if(p == -1){
			if(aqua[0] > 0){
				ans[i] += min(aqua[0],x);
				x -= aqua[0];
				if(x > 0) ans[i+1] += x;
			}
			else{
				ans[i+1] += min(llabs(aqua[0]),x);
				x -= llabs(aqua[0]);
				if(x > 0) ans[i] += x;
			}
		}
		else{
			if(aqua[p] > 0){
				ans[i] += aqua[p]+x-dm[p];
				ans[i+1] += llabs(aqua[p+1]);
			}
			else{
				ans[i] += aqua[p+1];
				ans[i+1] += llabs(aqua[p])+x-dm[p];
			}
		}
	}
	ans[1] += curam;
	ans[n] += curd;
	for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
}

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