Submission #132331

#	Time	Username	Problem	Language	Result	Execution time	Memory
132331		Noam527	Shortcut (IOI16_shortcut)	C++17	100 / 100	1363 ms	69880 KiB

shortcut

//#include "shortcut.h"
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

const int mxn = 1e6 + 5;

int n;
ll c;
ll a[mxn] = {}, b[mxn] = {};
bool check[mxn] = {}, check2[mxn] = {};

pair<ll, ll> st[mxn];

pair<ll, ll> calc12(ll D) {
	int sz = 0, nxt1 = 0, nxt2 = 0;
	ll rtn1 = -inf, rtn2 = -inf;
	st[sz++] = { a[0] + b[0], -a[0] + b[0] };
	for (int j = 1; j < n; j++) {
		if (check[j]) {
			nxt2 = min(nxt2, sz - 1);
			while (nxt2 + 1 < sz && c - D + st[nxt2].first - a[j] + b[j] <= rtn2) nxt2++;
			if (c - D + st[nxt2].first - a[j] + b[j] > rtn2) {
				if (st[nxt2].second + a[j] + b[j] > D) {
					while (nxt2 + 1 < sz && st[nxt2 + 1].second + a[j] + b[j] > D) nxt2++;
					rtn2 = max(rtn2, c - D + st[nxt2].first - a[j] + b[j]);
				}
			}
		}
		if (check2[j]) {
			while (nxt1 + 1 < sz && st[nxt1 + 1].second > D - b[j] - a[j]) nxt1++;
			while (nxt1 && st[nxt1].second <= D - b[j] - a[j]) nxt1--;
			if (st[nxt1].second > D - b[j] - a[j])
				rtn1 = max(rtn1, c - D + st[nxt1].first + a[j] + b[j]);
		}
		if (st[sz - 1].first < a[j] + b[j]) {
			while (sz && st[sz - 1].second <= -a[j] + b[j]) sz--;
			st[sz++] = { a[j] + b[j], -a[j] + b[j] };
		}
	}
	return{ rtn1, rtn2 };
}
pair<ll, ll> calc34(ll D) {
	ll rtn3 = inf, rtn4 = inf;
	ll mx = b[0] - a[0];
	for (int j = 1; j < n; j++) {
		if (mx > D - b[j] - a[j]) {
			rtn3 = min(rtn3, D - c - mx + a[j] - b[j]);
			rtn4 = min(rtn4, D - c - mx - a[j] - b[j]);
		}
		mx = max(mx, b[j] - a[j]);
	}
	return{ rtn3, rtn4 };
}
bool can(ll v[5]) {
	ll d[2] = { v[2], v[4] };
	ll s[2] = { v[1], v[3] };
	if (d[0] > d[1] || s[0] > s[1]) return false;

	int dl = 0, dr = 0, sl = n - 1, sr = n - 1; // difference applies on [dl, dr), sum on (sl, sr]
	for (int i = 0; i < n; i++) {
		dl = max(dl, i + 1);
		dr = max(dr, i + 1);
		if (dl > sr) return false;
		while (dl < n && a[i] - a[dl] > d[1]) dl++;
		while (dr < n && a[i] - a[dr] >= d[0]) dr++;
		while (sl > 0 && a[i] + a[sl] >= s[0]) sl--;
		while (sr > 0 && a[i] + a[sr] > s[1]) sr--;
		if (max(dl, sl + 1) <= min(dr - 1, sr))
			return true;
	}
	return false;
}

long long find_shortcut(int _n, std::vector<int> _l, std::vector<int> _d, int _c) {
	n = _n;
	c = _c;
	for (int i = 1; i < n; i++) {
		a[i] = _l[i - 1];
		a[i] += a[i - 1];
	}
	for (int i = 0; i < n; i++) b[i] = _d[i];

	check[n - 1] = true;
	ll mmx = -a[n - 1] + b[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		if (-a[i] + b[i] > mmx) {
			mmx = -a[i] + b[i];
			check[i] = true;
		}
	}
	check2[n - 1] = true;
	mmx = a[n - 1] + b[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		if (a[i] + b[i] > mmx) {
			mmx = a[i] + b[i];
			check2[i] = true;
		}
	}

	ll v[5];
	ll lo = 0, hi = 1000000000LL * (n + 2), mid;
	pair<ll, ll> p;
	while (lo < hi) {
		mid = (lo + hi) / 2;
		p = calc34(mid);
		v[3] = p.first;
		v[4] = p.second;
		p = calc12(mid);
		v[1] = p.first;
		v[2] = p.second;
		if (can(v)) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}

• 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: 3 / 3