Submission #960931

#	Time	Username	Problem	Language	Result	Execution time	Memory
960931		happy_node	Snowball (JOI21_ho_t2)	C++17	100 / 100	94 ms	15444 KiB

Main

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

const int MX=2e5+5;

int N,Q;
ll X[MX],W[MX],ans[MX],L[MX],R[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>Q;
	for(int i=1;i<=N;i++) cin>>X[i];
	ll sum=0;
	for(int i=1;i<=Q;i++) {
		cin>>W[i];
		sum+=W[i];
		L[i]=min(L[i-1],sum);
		R[i]=max(R[i-1],sum);
	}

	for(int i=1;i<N;i++) {
		int l=0,r=Q,res=0;
		while(l<=r) {
			int m=(l+r)/2;
			if(R[m]-L[m]<X[i+1]-X[i]) {
				l=m+1,res=m;
 			} else {
 				r=m-1;
 			}
		}
		ans[i]+=R[res];
		ans[i+1]-=L[res];
		if(res==Q) continue;
		
		if(W[res+1]>0) 
			ans[i]+=(X[i+1]-X[i])-(R[res]-L[res]);
		else
			ans[i+1]+=(X[i+1]-X[i])-(R[res]-L[res]);
	}

	ans[1]-=L[Q];
	ans[N]+=R[Q];

	for(int i=1;i<=N;i++) cout<<ans[i]<<'\n';
}

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