Submission #603115

#	Time	Username	Problem	Language	Result	Execution time	Memory
603115		8e7	Shortcut (IOI16_shortcut)	C++17	97 / 100	2080 ms	102076 KiB

shortcut

#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<58;
ll p[maxn], lef[maxn], rig[maxn], tmp[maxn], vl[maxn], vr[maxn];
pii ls[maxn], rs[maxn], a[maxn];

long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
	//vector<ll> p(n), lef(n+1, -inf), rig(n+1, -inf), tmp(n), vl(n+1, -inf), vr(n+1, -inf);
	//vector<pii> ls(n), rs(n), a(n);
	vl[n] = -inf, vr[n] = -inf;
	for (int i = 1;i < n;i++) p[i] = p[i-1] + L[i-1];
	for (int i = 0;i < n;i++) {
		a[i] = {p[i] + D[i], i};
		vl[i] = D[i] - p[i];
		vr[i] = D[i] + p[i];
	}
	sort(a, a + n);
	for (int i = 0;i < n;i++) {
		int id = a[i].ss;
		lef[i] = D[id] - p[id];
		rig[i] = D[id] + p[id];
		ls[i] = {id, n};
		rs[i] = {id, n};
	}
	for (int i = n - 2;i >= 0;i--) {
		int se = ls[i].ff;
		if (vl[ls[i+1].ff] < vl[se]) {
			se = ls[i+1].ff;
		} else {
			ls[i].ff = ls[i+1].ff;
		}
		if (vl[se] > vl[ls[i+1].ss]) ls[i].ss = se;
		else ls[i].ss = ls[i+1].ss;

		se = rs[i].ff;
		if (vr[rs[i+1].ff] < vr[se]) {
			se = rs[i+1].ff;
		} else {
			rs[i].ff = rs[i+1].ff;
		}
		if (vr[se] > vr[rs[i+1].ss]) rs[i].ss = se;
		else rs[i].ss = rs[i+1].ss;
	}	
	ll low = 0, up = (1LL<<30) * n * 2;
	while (low < up - 1) {
		ll M = (low + up) / 2;
		ll lb = -inf, rb = inf, db = -inf, ub = inf;
		
		for (int i = 0;i < n-1;i++) {
			int ind = upper_bound(rig, rig + n, M - (D[i] - p[i])) - rig;
			//[ind, n);
			if (ind == n) continue;
			ll len = M - D[i] - C;
			ll l = (rs[ind].ff != i ? vr[rs[ind].ff] : vr[rs[ind].ss]) - len, 
			   r = -(ls[ind].ff != i ? vl[ls[ind].ff] : vl[ls[ind].ss]) + len;
			//square with two points at [l, r]
			lb = max(lb, p[i] - r);
			rb = min(rb, p[i] - l);
			db = max(db, p[i] + l);
			ub = min(ub, p[i] + r);
			if (rb < lb || ub < db) break;
		}
		if (rb < lb || ub < db) low = M;
		else {
			bool good = 0;
			int ind = n-1;	
			for (int i = 0;i < n;i++) {
				ll mi = max(db - p[i], -rb + p[i]);
				if (p[ind] < mi) continue;
				ll ma = min(ub - p[i], -lb + p[i]);
				while (ind > 0 && p[ind-1] >= mi) ind--;
				if (p[ind] >= mi && p[ind] <= ma) {
					good = 1;
					break;
				}
			}	
			if (!good) {
				ind = n - 1;
				for (int i = n - 1;i >= 0;i--) {
					ll mi = max(db - p[i], -rb + p[i]);
					if (p[ind] < mi) continue;
					ll ma = min(ub - p[i], -lb + p[i]);
					while (ind > 0 && p[ind-1] >= mi) ind--;
					if (p[ind] >= mi && p[ind] <= ma) {
						good = 1;
						break;
					}
				}
			}
			if (good) up = M;
			else low = M;
		}
	}
	return up;
}
/*
2 4
10
28 37


2 1 
3
7 2
*/

• 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