Submission #738911

#	Time	Username	Problem	Language	Result	Execution time	Memory
738911		vjudge1	Safety (NOI18_safety)	C++17	100 / 100	103 ms	7008 KiB

safety

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const ll MOD=998244353;
ll N,M,a[200005];
struct SlopeTrick{
	ll minimum=0,negStart=0,posStart=0;
	priority_queue <ll> negSlope;
	priority_queue <ll,vector<ll>,greater<ll> > posSlope;
	void PrefixMin(){
		posStart=0;
		while(!posSlope.empty()){
			posSlope.pop();
		}
	}
	void SuffixMin(){
		negStart=0;
		while(!negSlope.empty()){
			negSlope.pop();
		}
	}
	void addPos(ll x){
		ll y;
		if(negSlope.empty()){
			y=-1e18;
		}
		else{
			y=negSlope.top()+negStart;
		}
		if(x>=y||negSlope.empty()){
			posSlope.push(x-posStart);
		}
		else{
			minimum+=y-x;
			negSlope.push(x-negStart);
			negSlope.pop();
			posSlope.push(y-posStart);
		}
	}

	void addNeg(ll x){
		ll y;
		if(posSlope.empty()){
			y=-1e18;
		}
		else{
			y=posSlope.top()+posStart;
		}
		if(x<=y||posSlope.empty()){
			negSlope.push(x-negStart);
		}
		else{
			minimum+=x-y;
			posSlope.push(x-posStart);
			posSlope.pop();
			negSlope.push(y-negStart);
		}
	}

	void RangeMin(ll l, ll r){
		if(!negSlope.empty()){
			negStart-=r;
		}
		if(!posSlope.empty()){
			posStart+=l;
		}
	}
};
int main(){
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	SlopeTrick dp=SlopeTrick();
	for(int i=1;i<=N;i++){
		dp.RangeMin(M,M);
		dp.addPos(a[i]);
		dp.addNeg(a[i]);
	}
	cout<<dp.minimum<<endl;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29