Submission #959004

#	Time	Username	Problem	Language	Result	Execution time	Memory
959004		MinaRagy06	Shortcut (IOI16_shortcut)	C++17	97 / 100	2025 ms	93624 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const int N = 1'000'005;
const ll inf = 1e18;
ll prf[N], vals[N];
ll s[N], d[N];
array<ll, 3> vals2[N];
int order[N], l[N], a[N];
ll find_shortcut(int n, vector<int> _l, vector<int> _a, int c) {
	for (int i = 1; i < n; i++) {
		l[i] = _l[i - 1];
		a[i] = _a[i - 1];
	}
	a[n] = _a[n - 1];
	l[n] = 0;
	prf[1] = 1;
	for (int i = 2; i <= n; i++) {
		prf[i] = prf[i - 1] + l[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		vals[i] = prf[i];
	}
	sort(vals + 1, vals + n + 1);
	for (int i = 1; i <= n; i++) {
		s[i] = prf[i] + a[i];
		d[i] = prf[i] - a[i];
	}
	for (int i = 1; i <= n; i++) {
		vals2[i] = {prf[i] + a[i], s[i], d[i]};
	}
	sort(vals2 + 1, vals2 + n + 1);
	for (int i = 1; i <= n; i++) {
		order[i - 1] = i;
	}
	sort(order, order + n, [&] (int x, int y) {return prf[x] - a[x] > prf[y] - a[y];});
	auto check = [&] (ll t) {
		ll l1 = -inf, r1 = inf, l2 = -inf, r2 = inf;
		int ptr = n;
		ll mxs[2] = {-inf, -inf}, mnd[2] = {inf, inf};
		for (int idx = 0; idx < n; idx++) {
			int i = order[idx];
			while (ptr > 0 && vals2[ptr][0] > t + prf[i] - a[i]) {
				mxs[1] = max(mxs[1], vals2[ptr][1]);
				if (mxs[0] < mxs[1]) swap(mxs[0], mxs[1]);
				mnd[1] = min(mnd[1], vals2[ptr][2]);
				if (mnd[0] > mnd[1]) swap(mnd[0], mnd[1]);
				ptr--;
			}
			ll sj = mxs[0], dj = mnd[0];
			if (prf[i] + a[i] > t + prf[i] - a[i]) {
				if (mxs[0] == s[i]) sj = mxs[1];
				if (mnd[0] == d[i]) dj = mnd[1];
			}
			l1 = max(l1, s[i] + sj - t + c);
			r1 = min(r1, d[i] + dj + t - c);
			l2 = max(l2, - d[i] + sj - t + c);
			r2 = min(r2, - s[i] + dj + t - c);
		}
		ptr = n;
		ll mn = 1e18;
		int lst = 0;
		for (int x = 1; x <= n; x++) {
			if (prf[x] > (l1 - l2) / 2) {
				break;
			}
			lst = x;
			ll st = l1 - vals[x];
			while (ptr > 0 && st <= vals[ptr]) {
				mn = min(mn, vals[ptr]);
				ptr--;
			}
			ll en = min(r1 - vals[x], r2 + vals[x]);
			if (mn <= en) {
				return true;
			}
		}
		ptr = n, mn = 1e18;
		for (int x = n; x > lst; x--) {
			ll st = l2 + vals[x];
			while (ptr > 0 && st <= vals[ptr]) {
				mn = min(mn, vals[ptr]);
				ptr--;
			}
			ll en = min(r1 - vals[x], r2 + vals[x]);
			if (mn <= en) {
				return true;
			}
		}
		return false;
	};
	ll st = 0, en = 2e15;
	while (st <= en) {
		ll md = (st + en) >> 1;
		if (check(md)) {
			en = md - 1;
		} else {
			st = md + 1;
		}
	}
	return st;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 0 / 3