Submission #33932

#	Time	Username	Problem	Language	Result	Execution time	Memory
33932		imeimi2000	Shortcut (IOI16_shortcut)	C++14	100 / 100	1949 ms	70424 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 = -1ll, se = -1ll;
	int fsi = -1, sei = -1, p, q;
	llong lad = -1e18, gad = 1e18, lsb = -1e18, gsb = 1e18;
	for (int i = 0, j = 0; i < n; ++i) {
		while (j < n && sb[j].first + m < ad[i].first) {
			p = sb[j].second;
			llong mx = dist[p] + etc[p];
			if (fs < mx) {
				sei = fsi;
				fsi = p;
				se = fs;
				fs = mx;
			}
			else if (se < mx) sei = p, se = mx;
			++j;
		}
		p = ad[i].second;
		if (p == sb[0].second && j == 1 || j == 0) continue;
		llong adi = (p == fsi ? se : fs);
		llong sbi = (p == sb[0].second ? sb[1].first : sb[0].first);
		llong adj = dist[p] + etc[p];
		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, lpos;
	p = 0, q = n - 1;
	for (int i = 0; i < n; ++i) {
		gpos = min(dist[i] - lsb, gad - dist[i]);
		lpos = max(dist[i] - gsb, lad - dist[i]);
		while (p > 0 && dist[p - 1] >= lpos) --p;
		while (p < n && dist[p] < lpos) ++p;
		while (q >= 0 && dist[q] > gpos) --q;
		while (q < n - 1 && dist[q + 1] <= gpos) ++q;
		if (p <= q) return true;
	}
	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;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool check(llong)':
shortcut.cpp:30:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (p == sb[0].second && j == 1 || j == 0) continue;
                         ^
shortcut.cpp:14:16: warning: variable 'sei' set but not used [-Wunused-but-set-variable]
  int fsi = -1, sei = -1, p, q;
                ^

• 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