Submission #1194398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194398		franuch	Text editor (CEOI24_editor)	C++20	100 / 100	374 ms	40208 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define vc vector
#define pub push_back
#define pob pop_back
#define st first
#define nd second
const ll INF = 1e18l;

struct Tree {
	ll base;
	vc<ll> t;
	Tree() = default;
	Tree(vc<ll> &a) {
		base = 1;
		while (base < sz(a))
			base *= 2;
		t.assign(2 * base, INF);
		for (ll i = 0; i < sz(a); i++)
			t[i + base] = a[i];
		for (ll i = base - 1; i >= 1; i--)
			t[i] = min(t[2 * i], t[2 * i + 1]);
	}

	ll query(ll l, ll r) {
		if (r < l)
			swap(l, r);
		l += base - 1;
		r += base + 1;
		ll ret = INF;
		while (l + 1 < r) {
			if (l % 2 == 0)
				ret = min(ret, t[l + 1]);
			if (r % 2 == 1)
				ret = min(ret, t[r - 1]);
			l /= 2;
			r /= 2;
		}
		return ret;
	}
};
Tree rmq;

void roz(vc<ll> &b) {
	ll n = sz(b);
	ll x = b[0];
	for (ll i = 1; i < n; i++) {
		x++;
		x = b[i] = min(x, b[i]);
	}
}

void stoz(vc<ll> &a, vc<ll> &b, ll si, ll sj) {
	ll n = sz(a);
	b.assign(n, INF);
	b[si] = sj;
	for (ll i = 0; i + 1 < n; i++)
		b[i + 1] = min(b[i + 1], abs(si - i) + a[i] - min(rmq.query(i, si), sj) + 1);
	for (ll i = 0; i < n; i++)
		b[i] = min(b[i], abs(si - i) + rmq.query(i, si));
	roz(b);
	reverse(all(b));
	roz(b);
	reverse(all(b));
}

void ztot(vc<ll> &a, vc<ll> &b, ll ti, ll tj) {
	ll n = sz(a);
	b.assign(n, INF);
	b[ti] = tj;
	for (ll i = 1; i < n; i++)
		b[i] = min(b[i], abs(i - 1 - ti) + abs(tj - rmq.query(i - 1, ti)) + 1);
	roz(b);
	reverse(all(b));
	roz(b);
	reverse(all(b));
}

void program() {
	ll n;
	cin >> n;
	ll si, sj, ti, tj;
	cin >> si >> sj >> ti >> tj;
	si--, sj--, ti--, tj--;
	vc<ll> a(n);
	for (ll &ai : a)
		cin >> ai;
	rmq = Tree(a);

	vc<ll> p, q;
	stoz(a, p, si, sj);
	ztot(a, q, ti, tj);
	ll ans = INF;
	for (ll i = 0; i < n; i++)
		ans = min(ans, p[i] + q[i]);
	/*
	for (ll &pi : p)
		cout << pi << " ";
	cout << "\n";
	for (ll &qi : q)
		cout << qi << " ";
	cout << "\n";
	*/
	ans = min(ans, abs(ti - si) + abs(tj - min(rmq.query(si, ti), sj)));
	for (ll i = 0; i < min(si, ti); i++)
		ans = min(ans, abs(ti - si) + 2 * (min(si, ti) - i) + abs(tj - min(rmq.query(i, max(si, ti)), sj)));
	for (ll i = max(si, ti) + 1; i < n; i++)
		ans = min(ans, abs(ti - si) + 2 * (i - max(si, ti)) + abs(tj - min(rmq.query(min(si, ti), i), sj)));
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	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