Submission #1083066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083066		mychecksedad	Text editor (CEOI24_editor)	C++17	100 / 100	769 ms	355476 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define en cout << '\n'
const int N = 1e6+1, NODE=2e6+100, K = 20;
ll INF = 1e18;

int n, sx, sy, ex, ey, rmq[N][K];
ll L[N];
vector<pair<int, ll>> g[NODE];

int get(int l, int r){
	if(l>r) return get(r, l);
	int k = int(log2(r-l+1));
	return min(rmq[l][k], rmq[r-(1<<k)+1][k]);
}

void solve(){
	cin >> n >> sx >> sy >> ex >> ey;
	for(int i = 1; i <= n; ++i) cin >> L[i];
	int source = 2*n + 1, sink = 2*n + 2;
	for(int i = 1; i <= n; ++i){
		g[i*2].pb({2*i - 1, L[i]});
		g[2*i-1].pb({2*i, L[i]});
		if(i < n){
			g[i*2-1].pb({2*i+1, 1});
			g[i*2+1].pb({2*i-1, 1});
			if(L[i] <= L[i + 1]){
				g[i*2].pb({2*i+2, 1 + abs(L[i + 1] - L[i])});
				g[i*2+2].pb({2*i, 1});
			}else{
				g[i*2+2].pb({2*i, 1 + abs(L[i + 1] - L[i])});
				g[i*2].pb({2*i+2, 1});
			}
			g[2*i+1].pb({2*i, 1});
			g[2*i].pb({2*i+1, 1});
		}
	}
	g[source].pb({2*sx - 1, sy - 1});
	g[2*sx - 1].pb({source, sy - 1});
	g[source].pb({2*sx, L[sx] - sy + 1});
	g[2*sx].pb({source, L[sx] - sy + 1});

	g[sink].pb({2*ex - 1, ey - 1});
	g[2*ex - 1].pb({sink, ey - 1});
	g[sink].pb({2*ex, L[ex] - ey + 1});
	g[2*ex].pb({sink, L[ex] - ey + 1});

	for(int i = 1; i <= n; ++i) rmq[i][0] = L[i] + 1;
	for(int j = 1; j < K; ++j){
		for(int i = 1; i + (1<<j) <= n + 1; ++i){
			rmq[i][j] = min(rmq[i][j - 1], rmq[i+(1<<(j-1))][j-1]);
		}
	}

	for(int i = 1; i <= n; ++i){
		if(get(i, sx) <= sy && L[i] + 1 == get(i, sx)){
			g[source].pb({2*i, abs(i-sx)});
		}
	}


	vector<ll> dist(sink + 5, INF);
	dist[source] = 0;
	ll ans = INF;
	vector<bool> used(sink + 1);
	priority_queue<pair<ll, int>> Q;
	Q.push({0, source});
	while(!Q.empty()){
		int v = Q.top().ss; Q.pop();
		if(used[v]) continue;
		used[v] = 1;
		for(auto U: g[v]){
			int u = U.ff;
			ll w = U.ss;
			if(!used[u] && dist[u] > dist[v] + w){
				dist[u] = dist[v] + w;
				Q.push({-dist[u], u});
			}
		}
	}

	// for(int i = 1; i <= n + 1; ++i){
	// 	cout << dist[i * 2 - 1] << ' '<< dist[2*i] << '\n';
	// }
	// cout << get(sx , ex) << "wtf";
	// cout << sy << ' ' << ey << "ff\n";
	if(sy <= get(sx, ex) && ey <= get(sx, ex)){
		ans = abs(sx-ex) + abs(sy-ey);
	}
	ans=min(ans, dist[sink]);
	for(int i = 1; i <= n; ++i){
		if(get(i, ex) == L[i] + 1){
			// cout << dist[2*i]+abs(ey-L[i])+abs(i-ex) << '\n';
			// cout << abs(ey-(L[i]+1)) << ' ' << abs(i-ex) << ' ' << i << '\n';
			ans=min(ans,dist[2*i]+abs(ey-(L[i]+1))+abs(i-ex));
		}
	}


	cout << ans;
}

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
  return 0;
}

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