Submission #1047155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047155		alex_2008	Text editor (CEOI24_editor)	C++14	100 / 100	262 ms	105044 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int l[N];
int st[N][21];
int lg2[N];
int mn[N];
void precalc() {
	lg2[1] = 0;
	for (int i = 2; i < N; i++) {
		lg2[i] = lg2[i / 2] + 1;
	}
}
int min_in_range(int l, int r) {
	int w = lg2[r - l + 1];
	return min(st[l][w], st[r - (1 << w) + 1][w]);
}
int main() {
	precalc();
	int n;
	cin >> n;
	int sl, sc, el, ec;
	cin >> sl >> sc >> el >> ec;
	for (int i = 1; i <= n; i++) {
		cin >> l[i];
		l[i]++;
	}
	for (int i = n; i >= 1; i--) {
		st[i][0] = l[i];
		for (int j = 1; j < 20; j++) {
			int pos = min(n, i + (1 << (j - 1)));
			st[i][j] = min(st[i][j - 1], st[pos][j - 1]);
		}
	}
	int ans = 1000000000 + n + 10;
	for (int i = 1; i <= n; i++) {
		int cur = 0;
		cur += abs(sl - i);
		cur += abs(i - el);
		int c = min({ sc, min_in_range(min(i, sl), max(i, sl)), min_in_range(min(i, el), max(i, el)) });
		cur += abs(c - ec);
		ans = min(ans, cur);
	}
	for (int i = 1; i <= n; i++) {
		mn[i] = abs(sl - i) + min(min_in_range(min(i, sl), max(i, sl)), sc) - 1;
		if (i > 1) {
			mn[i] = min(mn[i], abs(sl - (i - 1)) + l[i - 1] + 1 - min(sc, min_in_range(min(i - 1, sl), max(i - 1, sl))));
		}
	}
	for (int i = 2; i <= n; i++) {
		mn[i] = min(mn[i], mn[i - 1] + 1);
	}
	for (int i = n - 1; i >= 1; i--) {
		mn[i] = min(mn[i], mn[i + 1] + 1);
	}
	ans = min(ans, mn[el] + ec - 1);
	for (int i = 2; i <= n; i++) {
		//(i - 1, l[i])
		int cur = mn[i] + 1;
		cur += abs(el - (i - 1));
		int c = min_in_range(min(i - 1, el), max(i - 1, el));
		cur += abs(c - ec);
		ans = min(ans, cur);
	}
	cout << ans << "\n";
}

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