oj.uz

답안 #944337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944337 2024-03-12T15:04:25 Z dsyz Snowball (JOI21_ho_t2) C++17
0 / 100
 1 ms 348 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -