Submission #493787

#	Time	Username	Problem	Language	Result	Execution time	Memory
493787		nathanlee726	Snowball (JOI21_ho_t2)	C++14	100 / 100	345 ms	18620 KiB

Main

#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define int ll
#define pii pair<int,int>
#define X first
#define Y second
#define F(n) Fi(i,n) 
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define abs(x) ((x)>0?(x):-(x))
#define pb push_back

pii rg[200010];
int a[200010],b[200010],mr[200010],ml[200010],n,q;
vector<int> v;

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	F(n)cin>>a[i];
	F(q)cin>>b[i];
	mr[0]=0,ml[0]=0;
	int no=0;
	F(q){
		no+=b[i];
		mr[i+1]=max(mr[i],no);
		ml[i+1]=max(ml[i],-no);
	}
	F(q+1){
		v.pb(ml[i]+mr[i]);
	}
	rg[0].X=ml[q];
	rg[n-1].Y=mr[q];
	F(n-1){
		if(v[q]<=a[i+1]-a[i]){
			rg[i].Y=mr[q];
			rg[i+1].X=ml[q];
			continue;
		}
		int d=upper_bound(all(v),a[i+1]-a[i])-v.begin()-1;
		if(b[d]>0){
			rg[i].Y=a[i+1]-a[i]-ml[d+1];
			rg[i+1].X=ml[d+1];
		}
		else{
			rg[i].Y=mr[d+1];
			rg[i+1].X=a[i+1]-a[i]-mr[d+1];
		}
	} 
	//F(n)cout<<rg[i].X<<" "<<rg[i].Y<<endl;

	F(n){
		cout<<rg[i].X+rg[i].Y<<endl;
	}
	return 0;
}

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