Submission #742794

#	Time	Username	Problem	Language	Result	Execution time	Memory
742794		LCJLY	Snowball (JOI21_ho_t2)	C++14	100 / 100	146 ms	13772 KiB

Main

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

#define int long long 
typedef pair<int,int>pii;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n,q;
	cin >> n >> q;
	int arr[n+5];
	arr[0]=-1e18;
	arr[n+1]=1e18;

	for(int x=1;x<=n;x++){
		cin >> arr[x];
	}

	int wind[q+2];
	int left[q+2];
	int right[q+2];
	left[0]=0;
	right[0]=0;
	wind[0]=0;
	for(int x=1;x<=q;x++){
		cin >> wind[x];
		wind[x]+=wind[x-1];
		left[x]=min(wind[x],left[x-1]);
		right[x]=max(wind[x],right[x-1]);
	}
	wind[q+1]=wind[q];
	
	// for(auto it:wind) cout << it << " ";
	// cout << " wind\n";
	// for(auto it:left) cout << it << " ";
	// cout << " left\n";
	// for(auto it:right) cout << it << " ";
	// cout << " right\n";

	int counter=0;
	for(int x=1;x<=n;x++){
		int hold=0;

		//left
		int l=0;
		int r=q;
		int mid;
		int best=0;

		while(l<=r){
			mid=(l+r)/2;
			if(arr[x]+left[mid]>=arr[x-1]+right[mid]){
				best=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		// cout << best << " best\n";

		hold+=(-left[best]);
		int hold2=wind[best+1]-wind[best];
		if(hold2<0){
			hold+=min(-hold2,(arr[x]+left[best]-arr[x-1]-right[best]));
		}
		// cout << hold << " hold\n";
		//right

		l=0;
		r=q;
		best=0;

		while(l<=r){
			mid=(l+r)/2;
			if(arr[x]+right[mid]<=arr[x+1]+left[mid]){
				best=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		// cout << best << " best2\n";
		hold+=right[best];
		hold2=wind[best+1]-wind[best];
		if(hold2>0){
			// cout << hold2 << " " << (arr[x+1]+left[best]-arr[x]-right[best]) << " *\n";
			hold+=min(hold2,(arr[x+1]+left[best]-arr[x]-right[best]));
		}
		// cout << hold << " hold\n";
		counter+=hold;
		// cout << hold << " " << x  << "\n";
		cout << hold << "\n";
	}

	// cout << counter;
}

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