제출 #944344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944344		dsyz	Snowball (JOI21_ho_t2)	C++17	100 / 100	835 ms	13832 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 + 1];
	for(ll i = 0;i < N;i++){
		cin>>X[i];
	}
	X[N] = 1e18;
	ll cur = 0, maxi = 0, mini = 0;
	ll pmin[Q], pmax[Q], wind[Q];
	for(ll q = 0;q < Q;q++){
		cin>>wind[q];
		cur += wind[q];
		maxi = max(maxi,cur);
		mini = min(mini,cur);
		pmax[q] = maxi;
		pmin[q] = -1 * mini;
	}
	ll prev = X[0] + mini;
	for(ll i = 0;i < N;i++){
		ll Lb = max(prev,X[i] + mini);
		ll low = X[i];
		ll high = X[i + 1] + 1;
		while(high - low > 1){
			ll mid = (high + low) / 2;
			ll tmp1 = lower_bound(pmax,pmax + Q,mid - X[i]) - pmax;
			ll tmp2 = lower_bound(pmin,pmin + Q,X[i + 1] - mid + 1) - pmin;
			if(tmp1 < tmp2){
				low = mid;
			}else{
				high = mid;
			}
		}
		cout<<low - Lb<<'\n';
		prev = low;
	}
}

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