Submission #1152776

#TimeUsernameProblemLanguageResultExecution timeMemory
1152776khangrlSnowball (JOI21_ho_t2)C++20
33 / 100
591 ms17744 KiB
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define int long long 
using namespace std;
int n, q, last;
//vector <int> ans (2000005, 0);
map<int,int>ans;
vector <pair <int, int> > dist;
signed main(){
	cin>>n>>q;
	for(int i=0; i<n; i++){
		int a;
		cin>>a;
		if(i==0){
			last=a;
			continue ;
		}
		dist.pb({a-last, i-1});
		last=a;
	}
	sort(dist.begin(), dist.end());
	int mn=0, mx=0, sum=0, j=0;
    for(int i=1; i<=q; i++){
		int a;
		cin>>a;
		if(a==0){
			continue ;
		}
		sum+=a;
		int mn1=min(mn, sum), mx1=max(mx, sum);
		while(dist[j].ff<=mx1-mn1 and j<n-1){
			ans[dist[j].ss]+=mx;
			ans[dist[j].ss+1]+=abs(mn);
			int diff=dist[j].ff-(mx-mn);
			if(mn1==mn){
				ans[dist[j].ss]+=diff;
			}
			else{
				ans[dist[j].ss+1]+=diff;
			}
		    j++;
		}
		mn=min(mn, sum);
		mx=max(mx, sum);
	}
    while(j<n-1){
        ans[dist[j].ss]+=mx;
        ans[dist[j].ss+1]+=abs(mn);
        j++;
    }
	ans[0]+=abs(mn);
	ans[n-1]+=mx;
	for(int i=0; i<n; i++){
		cout<<ans[i]<<endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...