Submission #1134484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134484		amunduzbaev	Text editor (CEOI24_editor)	C++20	0 / 100	0 ms	324 KiB

Main

#include "bits/stdc++.h"

using namespace std;

//~ #define int ll
typedef long long ll;
#define ar array

template<class T> bool umin(T& a, T b) { if(b < a) { a = b; return true; } return false; }
template<class T> bool umax(T& a, T b) { if(a < b) { a = b; return true; } return false; }

//~ const int mod = 1e9 + 7;
//~ void add(int& a, const int b){
	//~ a += b;
	//~ while(a >= mod) a -= mod;
	//~ while(a < 0) a += mod;
//~ }

const ll INF = 1e18;

void solve(){
	int n; cin >> n;
	
	ar<int, 2> s; cin >> s[0] >> s[1]; s[0]--;
	ar<int, 2> e; cin >> e[0] >> e[1]; e[0]--;
	
	vector<int> l(n);
	for(int i=0;i<n;i++){
		cin >> l[i];
	}
	
	const int C = 4;
	vector<vector<ar<int, 2>>> edges(C * n + 2);
	int s_ = C * n, e_ = s_ + 1;
	
	auto add = [&](int a, int b, int c){
		edges[a].push_back({b, c});
		edges[b].push_back({a, c});
	};
	vector<ar<int, 4>> c(n);
	
	for(int i=0;i<n;i++){
		auto& [b, x, y, z] = c[i];
		
		b = 0;
		x = l[i], y = l[i], z = l[i];
		if(i) umin(x, l[i - 1]);
		if(i + 1 < n) umin(z, l[i + 1]);
		
		int vb = C * i;
		add(vb, vb + 1, x);
		add(vb, vb + 2, y);
		add(vb, vb + 3, z);
		
		add(vb + 1, vb + 2, abs(x - y));
		add(vb + 1, vb + 3, abs(x - z));
		
		add(vb + 2, vb + 3, abs(y - z));
	}
	
	for(int i=0;i + 1 < n;i++){
		int a = C * i, b = a + C;
		add(a, b, 1);
		if(l[i] >= l[i + 1]) edges[a + 2].push_back({b + 2, 1});
		if(l[i] <= l[i + 1]) edges[b + 2].push_back({a + 2, 1});
		add(a + 2, b, 1);
	}
	
	auto extra = [&](int v, int id, int len){
		//~ cout<<v<<" "<<id<<" "<<len<<endl;
		int len_ = len;
		for(int i=id;i>=0;i--){
			if(umin(len, l[i])){
				edges[v].push_back({i * C + 3, abs(i - id)});
				break;
			}
			
			for(int k=0;k<4;k++){
				add(i * C + k, v, abs(c[i][k] - len) + abs(i - id));
			}
		}
		
		len = len_;
		for(int i=id + 1;i<n;i++){
			if(umin(len, l[i])){
				edges[v].push_back({i * C + 3, abs(i - id)});
				break;
			}
			
			for(int k=0;k<4;k++){
				add(i * C + k, v, abs(c[i][k] - len) + abs(i - id));
			}
		}
	};
	
	auto get_min = [&](int i, int j){
		if(i > j) swap(i, j);
		int mn = l[i];
		for(int k=i;k<=j;k++){
			umin(mn, l[k]);
		}
		return mn;
	};
	
	extra(s_, s[0], s[1]);
	extra(e_, e[0], e[1]);
	
	if(get_min(s[0], e[0]) >= max(s[1], e[1])){
		add(s_, e_, abs(s[1] - e[1]) + abs(s[0] - e[0]));
	}
	
	priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;
	vector<ll> dis(edges.size(), INF);
	pq.push({0, s_});
	dis[s_] = 0;
	//~ cout<<s_<<"\n";
	
	while(!pq.empty()){
		auto [D, u] = pq.top(); pq.pop();
		if(D > dis[u]) continue;
		//~ cout<<u<<" "<<dis[u]<<"\n";
		
		for(auto [x, c] : edges[u]){
			if(umin(dis[x], dis[u] + c)){
				//~ if(x == 11){ // 14
					//~ cout<<u<<" "<<u / C<<" "<<dis[u]<<"\n";
				//~ }
				pq.push({dis[x], x});
			}
		}
	}
	
	//~ cout<<"dis:\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<C;j++){
			//~ cout<<dis[i * C + j]<<" ";
		//~ }
	
		//~ cout<<"\n";
	//~ }
	//~ cout<<"C:\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<C;j++){
			//~ cout<<c[i][j]<<" ";
		//~ }
	
		//~ cout<<"\n";
	//~ }
	
	cout<<dis[e_]<<"\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int t = 1;
	
	//~ cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44