제출 #960931

#제출 시각아이디문제언어결과실행 시간메모리
960931happy_nodeSnowball (JOI21_ho_t2)C++17
100 / 100
94 ms15444 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...