Submission #1042896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042896		Tob	Text editor (CEOI24_editor)	C++14	100 / 100	957 ms	535036 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e6 + 7;
const ll inf = 1e18;

int n, stx, sty, enx, eny;
int h[N];
map <int, int> m[N];
ll dis[2*N];
vector <pii> adj[2*N];

void Edge(int ax, int ay, int bx, int by, int w = -1) {
	if (w == -1) w = abs(ax-bx)+abs(ay-by);
	int x = m[ax][ay], y = m[bx][by];
	adj[x].pb({y, w});
	adj[y].pb({x, w});
}

int main () {
	FIO;
	cin >> n >> stx >> sty >> enx >> eny;
	stx--; sty--; enx--; eny--;
	
	for (int i = 0; i < n; i++) cin >> h[i];
	
	if (stx == enx && sty == eny) {cout << 0; return 0;}
	
	int cnt = 0;
	m[stx][sty] = cnt++;
	m[enx][eny] = cnt++;
	
	for (int i = 0; i < n; i++) {
		if (m[i].find(0) == m[i].end()) m[i][0] = cnt++;
		if (m[i].find(h[i]) == m[i].end()) m[i][h[i]] = cnt++;
		Edge(i, 0, i, h[i]);
	}
	
	Edge(stx, 0, stx, sty);
	Edge(stx, sty, stx, h[stx]);
	Edge(enx, 0, enx, eny);
	Edge(enx, eny, enx, h[enx]);
	
	for (int i = 1; i < n; i++) {
		Edge(i, 0, i-1, 0);
		Edge(i, 0, i-1, h[i-1], 1);
	}
	
	vector <pii> sp = {{stx, sty}, {enx, eny}};
	
	vector <int> v;
	auto DO = [&](int i){
		int y = m[i][h[i]];
		while (!v.empty() && h[v.back()] >= h[i]) {
			int x = v.back();
			int z = m[x][h[x]];
			adj[y].pb({z, abs(i-x)+abs(h[i]-h[x])});
			adj[z].pb({y, abs(i-x)});
			v.pop_back();
		}
		for (int j = 0; j < 2; j++) {
			if (i == sp[j].F) {
				for (auto x : v) {
					int z = m[x][h[x]];
					adj[j].pb({z, abs(i-x)+max(0LL, h[x]-sp[j].S)});
					adj[z].pb({j, abs(i-x)+abs(sp[j].S-h[x])});
				}
			}
		}
		v.pb(i);
	};
	
	for (int i = 0; i < n; i++) DO(i);
	v.clear();
	for (int i = n-1; i >= 0; i--) DO(i);
	
	for (int i = 1; i < cnt; i++) dis[i] = inf;
	set <pii> s;
	s.insert({0, 0});
	while (!s.empty()) {
		auto p = s.begin();
		int x = p -> S;
		s.erase(p);
		for (auto y : adj[x]) {
			if (dis[x] + y.S < dis[y.F]) {
				if (dis[y.F] != inf) s.erase({dis[y.F], y.F});
				dis[y.F] = dis[x] + y.S;
				s.insert({dis[y.F], y.F});
			}
		}
	}
	
	if (stx > enx) {swap(stx, enx); swap(sty, eny);}
	
	int mn = 1e9;
	for (int i = stx; i <= enx; i++) mn = min(mn, h[i]);
	if (min(sty, eny) <= mn) dis[1] = min(dis[1], (ll)abs(stx-enx)+abs(sty-eny));
	
	cout << dis[1];

	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