Submission #1204826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204826		aquasocute	Snowball (JOI21_ho_t2)	C++20	0 / 100	1 ms	580 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 = 2e6+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);
	cout.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{
			ll ccc = megu.back();
		    megu.push_back(ccc+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(abs(it) > curam){
				aquaa.push_back(it);
				curam = abs(it);
			}
		}
	}
	for(int i = 0; i < 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.size()) aqua.push_back(aquaa.back());
	for(int i = 0; i < aqua.size()-1; i++) dm.push_back(abs(aqua[i])+abs(aqua[i+1]));
	sort(dm.begin(),dm.end());
	//for(auto it: dm) cout << it << " ";
	//cout << "\n";
//	if(aqua.size() <= 1){
//		cout << 0;
//		return 0;
//	}
    aqua.push_back(999999999);
    dm.push_back(4e18);
	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();
		p--;
		if(p == dm.size()-1 && p != -1){
			if(aqua[p] > 0){
				ans[i] += aqua[p];
				ans[i+1] += abs(aqua[p+1]);
			}
			else{
				ans[i] += aqua[p+1];
				ans[i+1] += abs(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(abs(aqua[0]),x);
				x -= abs(aqua[0]);
				if(x > 0) ans[i] += x;
			}
		}
		else{
			if(aqua[p] > 0){
				ans[i] += aqua[p]+x-dm[p];
				ans[i+1] += abs(aqua[p+1]);
			}
			else{
				ans[i] += aqua[p+1];
				ans[i+1] += abs(aqua[p])+x-dm[p];
			}
		}
	}
	ans[1] += curam;
	ans[n] += curd;
	for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
}

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