Submission #603205

#	Time	Username	Problem	Language	Result	Execution time	Memory
603205		Apiram	Snowball (JOI21_ho_t2)	C++14	100 / 100	160 ms	12856 KiB

Main

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	vector<long long>ans(n,0);
	vector<long long>pref_min(m + 1),pref_max(m + 1),pref(m + 1);
	pref_min[0] = 0;
	pref_max[0] = 0;
	pref[0]  = 0;
	for (int i = 0;i<m;++i){
		long long x;cin>>x;
		pref[i + 1]=x + pref[i];
		pref_max[i + 1] = pref[i + 1];
		pref_min[i + 1] = pref[i + 1];
	}
	for (int i = 0;i<m;++i){
		pref_min[i + 1] = min(pref_min[i],pref_min[i + 1]);
		pref_max[i + 1] = max(pref_max[i],pref_max[i + 1]);
	}
	for (int i = 0;i<n - 1;++i){
		int left = 0,right = m;
		int pos = m;
		while(left<=right){
			int mid = (left + right)>>1;
			if (arr[i] + pref_max[mid] >= arr[i + 1] + pref_min[mid]){
				right = mid - 1;
				pos = mid;
			}
			else left = mid + 1;
		}
		if (pref_max[pos] != pref[pos]){
			pos--;
		}
		//cout<<i<<" "<<pos<<'\n';
		long long temp = max(0LL,min(arr[i + 1] + pref_min[pos] - arr[i],pref_max[pos]));
		ans[i]+=temp;
		ans[i + 1]+=max(0LL,min(-pref_min[m],arr[i + 1] - temp - arr[i])); 
	}
	ans[n - 1]+=pref_max[m];
	ans[0]+=-pref_min[m];
	for (auto x:ans)cout<<x<<'\n';
	return 0;
}

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