Submission #33929

#	Time	Username	Problem	Language	Result	Execution time	Memory
33929		imeimi2000	Shortcut (IOI16_shortcut)	C++14	0 / 100	0 ms	1932 KiB

shortcut

#include "shortcut.h"
#include <algorithm>

using namespace std;
typedef long long llong;

int n, c;
vector<llong> dist;
vector<int> etc;
vector<pair<llong, int>> ad, sb;

bool check(llong m) {
	llong fs = 0ll, se = 0ll;
	int mxi = -1, sei = -1, p;
	llong lad = -1e18, gad = 1e18, lsb = -1e18, gsb = 1e18;
	for (int i = 0, j = 0; i < n; ++i) {
		while (j < m && sb[j].first + m < ad[i].first) {
			p = sb[j].second;
			llong mx = dist[p] + etc[p];
			if (fs < mx) {
				sei = mxi;
				mxi = p;
				se = fs;
				fs = mx;
			}
			else if (se < mx) sei = p, se = mx;
			++j;
		}
		p = (ad[i].second == mxi ? sei : mxi);
		if (p == -1) continue;
		llong adi = (ad[i].second == mxi ? se : fs);
		llong sbi = (ad[i].second == sb[0].second ? sb[1].first : sb[0].first);
		p = ad[i].second;
		llong adj = ad[i].first;
		llong sbj = dist[p] - etc[p];
		lsb = max(lsb, adi - sbj - m + c);
		gsb = min(gsb, sbi - adj + m - c);
		lad = max(lad, adi + adj - m + c);
		gad = min(gad, sbi + sbj + m - c);
	}
	llong gpos = -1e18, lpos = 1e18;
	for (int i = 0; i < n; ++i) {
		if (lpos <= dist[i] && dist[i] <= gpos) return true;
		gpos = max(gpos, min(dist[i] - lsb, gad - dist[i]));
		lpos = min(lpos, max(dist[i] - gsb, lad - dist[i]));
	}
	return false;
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C) {
	n = N; c = C;
	dist.resize(n);
	llong sum = 0ll;
	for (int i = 1; i < n; ++i) {
		sum += l[i - 1];
		dist[i] = sum;
	}
	etc = d;
	llong ld = 0ll, e = 0ll;
	int fs = 0, se = 0;
	for (int i = 0; i < n; ++i) {
		ad.push_back({ dist[i] + etc[i], i });
		sb.push_back({ dist[i] - etc[i], i });

		e = max(e, ld + etc[i]);

		if (fs < etc[i]) {
			se = fs;
			fs = etc[i];
		}
		else if (se < etc[i]) {
			se = etc[i];
		}

		if (i < n - 1)
			ld = max(ld, (llong)etc[i]) + l[i];
	}
	sort(ad.begin(), ad.end());
	sort(sb.begin(), sb.end());

	llong s = fs + se;
	while (s < e) {
		llong m = (s + e) / 2;
		if (check(m)) e = m;
		else s = m + 1ll;
	}
	return s;
}

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