Submission #1153118

#TimeUsernameProblemLanguageResultExecution timeMemory
1153118ezzzaySnowball (JOI21_ho_t2)C++20
33 / 100
368 ms20812 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int a[N];
int ans[N];
map< int, pair<int,int> > mp;
signed main(){
	int n,q;
	cin>>n>>q;
	int l=-1e17;
	vector<pair<int,int>>vc;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vc.pb({a[i]-l,i-1});
		l=a[i];
	}
	vc.pb({1e17,n});
	sort(vc.begin(),vc.end());
	int s=0,r=0,i=0;l=0;
	while(q--){
		int x;
		cin>>x;
		s+=x;
		if(s==0)continue;
		if(s>0){
			l=max(l,s);
			if(i==n+1)continue;
			while(l+r>=vc[i].ff){
				mp[vc[i].ss].ss=r;
				mp[vc[i].ss].ff=vc[i].ff-r;
				i++;
				if(i==n+1)break;
			}
		}
		else{
			r=max(r,abs(s));
			if(i==n+1)continue;
			while(i<=n and l+r>=vc[i].ff){
				mp[vc[i].ss].ff=l;
				mp[vc[i].ss].ss=vc[i].ff-l;
				i++;
				if(i==n+1)break;
			}
		}
	}
	while(i<=n){
		mp[vc[i].ss].ff=l;
	    mp[vc[i].ss].ss=r;
		i++;
	}
	for(int i=0;i<=n;i++){
		ans[i]+=mp[i].ff;
		ans[i+1]+=mp[i].ss;
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...