Submission #1182929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182929		PieArmy	Snowball (JOI21_ho_t2)	C++20	100 / 100	181 ms	11444 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

int n,q;
ll arr[200023];
pair<ll,ll>mx[200023],gain[200023];
ll loc=0;
ll ans[200023];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<=q;i++){
		mx[i]=mx[i-1];
		gain[i]=gain[i-1];
		ll x;cin>>x;
		loc+=x;
		mx[i].fr=min(mx[i].fr,loc);
		mx[i].sc=max(mx[i].sc,loc);
		gain[i].fr+=mx[i-1].fr-mx[i].fr;
		gain[i].sc+=mx[i].sc-mx[i-1].sc;
	}
	ans[1]-=mx[q].fr;
	ans[n]+=mx[q].sc;
	for(int i=1;i<n;i++){
		int l=0,r=q;
		while(l<r){
			int m=(l+r+1)/2;
			if(mx[m].sc-mx[m].fr<arr[i+1]-arr[i])l=m;
			else r=m-1;
		}
		ans[i]+=gain[l].sc;
		ans[i+1]+=gain[l].fr;
		if(l!=q){
			if(mx[l].fr==mx[l+1].fr){
				ans[i]+=arr[i+1]-arr[i]-gain[l].fr-gain[l].sc;
			}
			else{
				ans[i+1]+=arr[i+1]-arr[i]-gain[l].fr-gain[l].sc;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
}

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