Submission #1360259

#TimeUsernameProblemLanguageResultExecution timeMemory
1360259053thousandText editor (CEOI24_editor)C++20
0 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
	int a,b,c,d,e,f[1000005],g[1000005][2],y,x,yy,xx,ans=1e9;
	priority_queue<pair<int,pair<int,bool>>>p;
	void add(int x,int y,int z){
		if(y==-1)p.push({x,{y,z}});
		if(y>0 and y<=a and g[y][z]==-1)p.push({x,{y,z}});
	}
int main(){
	cin>>a;
	cin>>y>>x;
	cin>>yy>>xx;
	for(int i=1;i<=a;i++){
		cin>>f[i];
		f[i]++;
		g[i][0]=-1;
		g[i][1]=-1;
	}
	int cur=y;
	while(f[cur]>x and cur>0){
		if(cur==yy) ans=abs(xx-x)+abs(yy-y);
		add(1-x-abs(cur-y),cur,0);
		add(x-f[cur]-abs(cur-y),cur,1);
		cur--;
	}
	if(cur!=0) {
		add(-abs(cur-y),cur,1);
	}
    cur=y+1;
	while(f[cur]>x and cur<=a){
		if(cur==yy) ans=abs(xx-x)+abs(yy-y);
		add(1-x-abs(cur-y),cur,0);
		add(x-f[cur]-abs(cur-y),cur,1);
		cur++;
	}
	if(cur!=a+1){
		add(-abs(cur-y),cur,1);
	}
	while(!p.empty()){
		int p1=p.top().second.first,p3=p.top().first;
		bool p2=p.top().second.second;
		p.pop();
		if(g[p1][p2]==-1){
			if(f[p1]==0) g[p1][1-p2]=-g[p1][p2];
//			cout<<p1<<' '<<p2<<' '<<p3<<endl; 
			if(f[p1]==1) add(p3-1,p1,1-p2);
			g[p1][p2]=-p3;
			if(p2==0){
				add(p3-1,p1-1,0);
				add(p3-1,p1+1,0);
				add(p3-1,p1-1,1);
			}
			else{
				if(f[p1-1]<=f[p1]) add(p3-1,p1-1,1);
				if(f[p1-1]+1==f[p1]) add(p3-2,p1-1,1);
				if(f[p1+1]<=f[p1]) add(p3-1,p1+1,1);
				if(f[p1+1]+1==f[p1]) add(p3-2,p1+1,1);
				add(p3-1,p1+1,0);
			}
		}
	}
	ans=min(ans,g[yy][0]+xx-1);
//	for(int i=1;i<=a;i++) cout<<g[i][0]<<' '<<g[i][1]<<endl;
	cur=yy;
	int mi=f[yy];
	while(cur>0){
		mi=min(mi,f[cur]);
		ans=min(ans,g[cur][1]+abs(mi-xx)+abs(cur-yy));
		cur--;
	}
	mi=f[yy];
    cur=yy;
	while(cur<=a){
		mi=min(mi,f[cur	]);
		ans=min(ans,g[cur][1]+abs(mi-xx)+abs(cur-yy));
		cur++;
	}
	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...