Submission #377306

#	Time	Username	Problem	Language	Result	Execution time	Memory
377306		YJU	Snowball (JOI21_ho_t2)	C++14	100 / 100	176 ms	9836 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,q,u[N],loc,r[N],l[N],ans[N],x[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	u[0]=-INF,u[n+1]=INF;
	REP1(i,n)cin>>u[i];
	REP1(i,q){
		cin>>x[i];
		loc+=x[i];
		r[i]=max(r[i-1],loc);
		l[i]=min(l[i-1],loc);
	}
	ll L,R;
	REP1(i,n){
		L=0,R=q+1;
		while(R-L>1){
			ll mid=(R+L)>>1;
			if(u[i-1]+r[mid]<=u[i]+l[mid]){
				L=mid;
			}else{
				R=mid;
			}
		}
		if(i==1)ans[i]+=abs(l[L]);
		else ans[i]+=abs(l[L])+(x[L+1]<0?u[i]+l[L]-u[i-1]-r[L]:0);
		L=0,R=q+1;
		while(R-L>1){
			ll mid=(R+L)>>1;
			if(u[i]+r[mid]<=u[i+1]+l[mid]){
				L=mid;
			}else{
				R=mid;
			}
		}
		if(i==n)ans[i]+=abs(r[L]);
		else ans[i]+=abs(r[L])+(x[L+1]>0?u[i+1]+l[L]-u[i]-r[L]:0);
		cout<<ans[i]<<"\n";
	}
	return 0;
}

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