제출 #1335350

#제출 시각아이디문제언어결과실행 시간메모리
1335350WH8Text editor (CEOI24_editor)C++17
0 / 100
1 ms580 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define iii tuple<int,int,int>
#define sz(x) (int)x.size()

signed main(){
	int n;cin>>n;
	int sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;
	vector<int> l(n+1, 0);
	for(int i=1;i<=n;i++){
		cin>>l[i];
		l[i]++;
	}
	vector<array<vector<iii>, 2>> al(n+1);
	vector<int> stk;
	// 1-1 edges 
	vector<array<int,2>> d1(n+1), d2(n+1);
	for(int i=1;i<=n;i++){
		d1[i][0]=abs(i- sx)+sy-1, d1[i][1]=1e16;
		d2[i][0]=abs(i- tx)+ty-1, d2[i][1]=1e16;
	}
	int ans=1e18;
	for(int t=0;t<2;t++){
		int i, stop, delta;
		if(t==0)i=1, stop=n+1, delta=1;
		else i=n, stop=0, delta=-1;
		stk.clear();
		for(;i!=stop;i+=delta){
			while(!stk.empty() and l[stk.back()] >= l[i]){
				int pi=stk.back(), pl=l[pi];
				if(abs(pl-l[i]) <= 1){
					al[i][1].push_back(make_tuple(pi, 1, abs(pl-l[i]) + abs(i-pi)));
				}
				stk.pop_back();
			}
			// go down
			if(!stk.empty()){
				int pi=stk.back(), pl=l[pi];
				al[i][1].push_back(make_tuple(pi, 1, abs(pl-l[i]) + abs(i-pi)));
			}
			stk.push_back(i);
			if(i==sx){
				for(auto pi : stk){
					if(pi == tx){ // s and t are in the same block 
						ans=abs(sx-tx) + abs(sy-ty);
					}
					d1[pi][1]=abs(sx-pi) + max(0ll, l[pi]-sy);
				}
			}
			if(i==tx){
				for(auto pi : stk){
					d2[pi][1]=abs(tx-pi) + abs(ty-l[pi]);
				}
			}
		}
	}
	//0-0 edges
	for(int i=1;i<n;i++)al[i][0].push_back(make_tuple(i+1, 0, 1));
	for(int i=2;i<=n;i++)al[i][0].push_back(make_tuple(i-1, 0, 1));
	// 0-1 edges;
	for(int i=1;i<n;i++) al[i][1].push_back(make_tuple(i+1, 0, 1));
	for(int i=2;i<=n;i++)al[i][0].push_back(make_tuple(i-1, 1, 1));
	priority_queue<iii,vector<iii>,greater<iii>> pq;
	for(int i=1;i<=n;i++){
		pq.push({d1[i][0], i, 0});
		pq.push({d1[i][1], i, 1});
	}
	while(!pq.empty()){
		auto [cd, x, y]=pq.top(); pq.pop();
		if(d1[x][y] < cd) continue;
		for(auto [itx, ity, w] : al[x][y]){
			if(d1[itx][ity] <= cd + w)continue;
			d1[itx][ity]=cd+w;
			pq.push({d1[itx][ity], itx, ity});
		}
	}
	for(int i=1;i<=n;i++){
		ans=min(ans, d1[i][0] + d2[i][0]);
		ans=min(ans, d1[i][1] + d2[i][1]);
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...