Submission #923421

#TimeUsernameProblemLanguageResultExecution timeMemory
923421ting39Snowball (JOI21_ho_t2)C++17
100 / 100
386 ms12372 KiB
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
signed main(){
	int n,q;
	cin>>n>>q;
	vector<int> dif(n-1),ans(n);
	int pre;
	cin>>pre;
	for(int i=1;i<n;i++){
		cin>>dif[i-1];
		int tmp=pre;
		pre=dif[i-1];
		dif[i-1]-=tmp;
	}
	vector<int> vv(n-1);
	for(int i=0;i<n-1;i++) vv[i]=i;
	sort(vv.begin(),vv.end(),[&](int i,int j){
		return dif[i]<dif[j];
	});
	int pos=0,mn=0,mx=0,now=0;
	while(q--){
		int x;
		cin>>x;
		while(pos<n-1&&dif[vv[pos]]<=max(mx,now+x)-min(mn,now+x)){//cout<<ans[vv[pos]]<<' '<<ans[vv[pos]+1]<<endl;
			ans[vv[pos]]+=mx;
			ans[vv[pos]+1]-=mn;
			if(x>0) ans[vv[pos]]+=dif[vv[pos]]-mx+mn;
			else ans[vv[pos]+1]+=dif[vv[pos]]-mx+mn;//cout<<ans[vv[pos]]<<' '<<ans[vv[pos]+1]<<endl;
			pos++;
		}
		now+=x;
		mx=max(mx,now);
		mn=min(mn,now);
	}
	while(pos<n-1){
		ans[vv[pos]]+=mx;
		ans[vv[pos]+1]-=mn;
		pos++;
	}
	ans[0]-=mn;
	ans[n-1]+=mx;
	for(int i:ans) cout<<i<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...