Submission #371827

#	Time	Username	Problem	Language	Result	Execution time	Memory
371827		mariowong	Snowball (JOI21_ho_t2)	C++14	100 / 100	274 ms	8300 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long long n,q,a[200005],pt,lmax,rmax,mv,now,ans[200005],pos;
pair <long long,long long> gap[200005];
int main(){ 
	cin >> n >> q;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	for (int i=2;i<=n;i++){
		gap[i-1]=make_pair(a[i]-a[i-1],i);
	}
	sort(gap+1,gap+n);
	for (int i=1;i<=q;i++){
		cin >> mv;
		now+=mv;
		if (now < lmax){
			lmax=now;
			while (pt+1 < n && gap[pt+1].first <= -lmax+rmax){
				pt++; pos=gap[pt].second;
				ans[pos-1]+=rmax;
				ans[pos]+=a[pos]-a[pos-1]-rmax;
			}
		}
		else
		if (now > rmax){
			rmax=now;
			while (pt+1 < n && gap[pt+1].first <= -lmax+rmax){
				pt++; pos=gap[pt].second;
				ans[pos]+=-lmax;
				ans[pos-1]+=a[pos]-a[pos-1]-(-lmax);
			}
		}
	}
	for (int i=pt+1;i<n;i++){
		pos=gap[i].second;
		ans[pos-1]+=rmax;
		ans[pos]+=-lmax;
	}
	ans[1]+=-lmax;
	ans[n]+=rmax;
	for (int i=1;i<=n;i++){
		cout << ans[i] << "\n";
	}
    return 0;
}	
//pre_neg[i] store i to i+1 from right
//pre_pos[i] store i to i+1 from  left

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