Submission #1134583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134583		amunduzbaev	Text editor (CEOI24_editor)	C++20	100 / 100	3181 ms	891184 KiB

Main

#include "bits/stdc++.h"

using namespace std;

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

template<class T, class U> bool umin(T& a, U b) { if(b < a) { a = b; return true; } return false; }
template<class T, class U> bool umax(T& a, U 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;
const int inf = 1e9;

struct SparseTable{
	vector<int> a;
	vector<vector<int>> mn, mx;
	int N, M;
	
	SparseTable(vector<int> a): a(a){
		N = a.size();
		M = __lg(N) + 1;
		mn.resize(N, vector<int>(M));
		mx.resize(N, vector<int>(M));
		
		for(int i=0;i<N;i++){
			mx[i][0] = mn[i][0] = a[i];
		}
		
		for(int j=1;j<M;j++){
			for(int i=0;i + (1 << (j - 1)) < N;i++){
				mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
				mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	
	int min_(int l, int r){
		if(l > r) return inf;
		int lg = __lg(r - l + 1);
		return min(mn[l][lg], mn[r - (1 << lg) + 1][lg]);
	}
	
	int max_(int l, int r){
		if(l > r) return inf;
		int lg = __lg(r - l + 1);
		return max(mx[l][lg], mx[r - (1 << lg) + 1][lg]);
	}
};

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]--;
	s[1]--, e[1]--;
	
	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);
		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 + 2, 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 + 2, abs(i - id)});
				break;
			}
			
			for(int k=0;k<4;k++){
				add(i * C + k, v, abs(c[i][k] - len) + abs(i - id));
			}
		}
	};
	
	SparseTable st(l);
	
	auto getl = [&](int i, int v){
		int l_ = 0, r_ = i;
		while(l_ < r_){
			int m = (l_ + r_ + 1) >> 1;
			if(st.min_(m, i) < v) l_ = m;
			else r_ = m - 1;
		}
		
		if(st.min_(l_, i) < v) return l_;
		else return -1;
	};
	
	auto getr = [&](int i, int v){
		int l_ = i, r_ = n - 1;
		while(l_ < r_){
			int m = (l_ + r_) >> 1;
			
			if(st.min_(i, m) < v) r_ = m;
			else l_ = m + 1;
		}
		
		if(st.min_(i, l_) < v) return l_;
		else return -1;
	};
	
	for(int i=0;i<n;i++){
		int l_ = getl(i, l[i]);
		if(l_ != -1){
			//~ edges[l_ * C + 2].push_back({i * C + 2, abs(i - l_) + abs(l[l_] - l[i])});
			edges[i * C + 2].push_back({l_ * C + 2, abs(i - l_)});
		}
		
		int r = getr(i, l[i]);
		if(r != -1){
			//~ edges[r * C + 2].push_back({i * C + 2, abs(i - r) + abs(l[r] - l[i])});
			edges[i * C + 2].push_back({r * C + 2, abs(i - r)});
		}
	}
	
	extra(s_, s[0], s[1]);
	
	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;
	
	while(!pq.empty()){
		auto [D, u] = pq.top(); pq.pop();
		if(D > dis[u]) continue;
		
		for(auto [x, c] : edges[u]){
			if(umin(dis[x], dis[u] + c)){
				pq.push({dis[x], x});
			}
		}
	}
	
	ll ans = INF;
	if(st.min_(min(e[0], s[0]), max(e[0], s[0])) >= min(e[1], s[1])){
		umin(ans, abs(e[0] - s[0]) + abs(e[1] - s[1]));
	}
		
	for(int i=0;i<n;i++){
		int l_ = e[0], r = i;
		if(l_ > r) swap(l_, r);
		
		//~ cout<<
		if(st.min_(l_, r) >= min(e[1], l[i])){
			umin(ans, dis[i * C + 2] + abs(l_ - r) + abs(l[i] - e[1]) );
		}
		
		umin(ans, dis[i * C] + abs(l_ - r) + e[1]);
	}
	
	cout<<ans<<"\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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 11 / 11
• Subtask 5: 44 / 44