Submission #34074

#	Time	Username	Problem	Language	Result	Execution time	Memory
34074		imeimi2000	Shortcut (IOI16_shortcut)	C++14	100 / 100	1433 ms	60532 KiB

shortcut

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

using namespace std;
typedef long long llong;

const int max_n = 1e6;
int n, c;
llong dist[max_n];
int etc[max_n];
pair<llong, int> ad[max_n], sb[max_n];

bool check(llong m) {
	llong fs = -1ll, se = -1ll;
	int fsi = -1, sei = -1, p;
	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);
		if (lsb > gsb) return false;
		lad = max(lad, adi + adj - m + c);
		gad = min(gad, sbi + sbj + m - c);
		if (lad > gad) return false;
	}
	llong gpos, lpos;
	int q = -1;
	for (int i = 0; i < n - 1; ++i) {
		gpos = min(dist[i] - lsb, gad - dist[i]);
		lpos = max(dist[i] - gsb, lad - dist[i]);
		if (lpos > gpos) continue;
		while (q != -1 && dist[q] > gpos) --q;
		while (q < n - 1 && dist[q + 1] <= gpos) ++q;
		if (i < q && lpos <= dist[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;
	llong sum = 0ll;
	for (int i = 1; i < n; ++i) {
		sum += l[i - 1];
		dist[i] = sum;
	}
	llong ld = 0ll, e = 0ll;
	int fs = 0, se = 0;
	for (int i = 0; i < n; ++i) {
		etc[i] = d[i];
		ad[i] = { dist[i] + etc[i], i };
		sb[i] = { 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, ad + n);
	sort(sb, sb + n);

	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:31:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (p == sb[0].second && j == 1 || j == 0) continue;
                         ^
shortcut.cpp:15:16: warning: variable 'sei' set but not used [-Wunused-but-set-variable]
  int fsi = -1, sei = -1, p;
                ^

• 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