Submission #944337

#	Time	Username	Problem	Language	Result	Execution time	Memory
944337		dsyz	Snowball (JOI21_ho_t2)	C++17	0 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q;
	cin>>N>>Q;
	ll X[N];
	for(ll i = 0;i < N;i++){
		cin>>X[i];
	}
	ll cur = 0;
	ll pmin[Q], pmax[Q], wind[Q];
	for(ll q = 0;q < Q;q++){
		cin>>wind[q];
		cur += wind[q];
		if(q == 0){
			pmin[q] = cur;
			pmax[q] = cur;
		}else{
			pmin[q] = min(pmin[q - 1],cur);
			pmax[q] = max(pmax[q - 1],cur);
		}
	}
	for(ll q = 0;q < Q;q++){
		if(pmin[q] > 0) pmin[q] = 0;
		pmin[q] *= -1;
		if(pmax[q] < 0) pmax[q] = 0;
	}
	ll ans[N];
	memset(ans,0,sizeof(ans));
	for(ll i = 0;i < N;i++){
		//find left boundary
		if(i == 0){
			ans[i] += max(0ll,pmin[Q - 1]);
		}else{
			ll high = Q;
			ll low = -1;
			while(high - low > 1){
				ll mid = (high + low) / 2;
				if(X[i - 1] + pmax[mid] <= X[i] - pmin[mid]){
					low = mid;
				}else{
					high = mid;
				}
			}
			if(low >= 0){
				ans[i] += max(0ll,pmin[low]);
			}
		}
		
		//find right boundary
		if(i == N - 1){
			ans[i] += max(0ll,pmax[Q - 1]);
		}else{
			ll high = Q;
			ll low = -1;
			while(high - low > 1){
				ll mid = (high + low) / 2;
				if(X[i + 1] - pmin[mid] >= X[i] + pmax[mid]){
					low = mid;
				}else{
					high = mid;
				}
			}
			if(low >= 0){
				ans[i] += max(0ll,pmax[low]);
			}
		}
	}
	for(ll i = 0;i < N;i++){
		cout<<ans[i]<<'\n';
	}
}

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