제출 #1288209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288209		WH8	Snowball (JOI21_ho_t2)	C++20	100 / 100	175 ms	13068 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())

signed main(){
	int n,m;cin>>n>>m;
	vector<int> pos(n+2), l(n+2, 0), r(n+2, 0);
	pos[0]=LLONG_MIN/2;
	pos[n+1]=LLONG_MAX/2;
	for(int i=1;i<=n;i++){
		cin>>pos[i];
	}
	vector<int> ps(m+1, 0), mx(m+1, 0), mn(m+1, 0), sm(m+1, 0);
	for(int i=1;i<=m;i++){
		int c;cin>>c;
		ps[i]=ps[i-1]+c;
		mx[i]=max(mx[i-1],ps[i]);
		mn[i]=min(mn[i-1],ps[i]);
		sm[i]=abs(mx[i])+abs(mn[i]);
	}
	for(int i=0;i<=n;i++){
		int gap=pos[i+1]-pos[i];
		int t=lower_bound(sm.begin(),sm.end(),gap)-sm.begin();
		if(t==m+1){
			r[i]=mx[t-1];
			l[i+1]=mn[t-1];
		}
		else{
			if(mx[t-1]!=mx[t]){
				l[i+1]=mn[t-1];
				r[i]=gap-abs(mn[t-1]);
			}
			else {
				r[i]=mx[t-1];
				l[i+1]=-(gap-abs(mx[t-1]));
			}
		}
	}
	for(int i=1;i<=n;i++){
		//~ printf("i %lld, l %lld r %lld\n", i, l[i], r[i]);
		cout<<r[i]-l[i]<<'\n';
	}
}

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