제출 #1335370

#제출 시각아이디문제언어결과실행 시간메모리
1335370WH8Text editor (CEOI24_editor)C++17
100 / 100
1670 ms449500 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)));
				}
				if(i==sx) d1[pi][1]=abs(sx-pi)+abs(l[pi]-sy);
				if(i==tx) d2[pi][1]=abs(tx-pi)+abs(l[i]-ty); // drop down
				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){
					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]);
				}
			}
		}
	}
	int mn=1e18;
	for(int i=min(sx, tx); i<=max(sx, tx);i++){
		mn=min(l[i], mn);
	}
	if(mn >= min(sy, ty)){
		ans=min(ans, abs(sx-tx)+abs(sy-ty));
	}
	//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));
	// same row edge: 
	for(int i=1;i<=n;i++){
		al[i][1].push_back(make_tuple(i, 0, l[i]-1));
		al[i][0].push_back(make_tuple(i, 1, l[i]-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});
	}

	//cout<<ans<<endl;
	/*for(int i=1;i<=n;i++){
		cout<<d1[i][0]<<" "<<d1[i][1]<<" "<<d2[i][0]<<" "<<d2[i][1]<<endl;
	}*/
	//for(auto [itx,ity, w] : al[2][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...