Submission #60819

#	Time	Username	Problem	Language	Result	Execution time	Memory
60819		kingpig9	Shortcut (IOI16_shortcut)	C++11	97 / 100	1636 ms	145784 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> edge;
const int MAXN = 3e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}

int N;
ll C;
ll L[MAXN];	//total length
ll D[MAXN];	//distance to secondary station (i + N)

//max BIT - wow that actually sped things up!
struct fenwick {
	ll bit[MAXN];

	void reset() {
		fill_n(bit, MAXN, LLONG_MIN);
	}

	void update (int x, ll v) {
		for (x++; x < MAXN; x += (x & -x)) {
			setmax(bit[x], v);
		}
	}

	ll query (int x) {
		//query to x EXCLUSIVE
		ll res = LLONG_MIN;
		for (; x; x &= (x - 1)) {
			setmax(res, bit[x]);
		}
		return res;
	}
};

fenwick fenlpd, fendml;
pair<ll, int> vlmd[MAXN], vlpd[MAXN];
ll qdml[MAXN];

bool moo (ll dia) {
	//debug("DIA = %lld\n", dia);
	ll xmymn = LLONG_MIN, xmymx = LLONG_MAX;
	ll xpymn = LLONG_MIN, xpymx = LLONG_MAX;

	//reset entire fenwick tree
	fenlpd.reset();
	//fendml.reset();
	for (int i = 0; i <= N; i++) {
		qdml[i] = LLONG_MIN;
	}
	//once you add dml to a range, it never changes.

	/*
	for (int i = 0; i < N; i++) {
		debug("vlpd[%d] = (%lld, %d)\n", i, vlpd[i].fi, vlpd[i].se);
	}
	for (int i = 0; i < N; i++) {
		debug("vlmd[%d] = (%lld, %d)\n", i, vlmd[i].fi, vlmd[i].se);
	}
	*/

	//vlpd[vj].fi - vlmd[vi].fi > dia
	int qdmlind = N;
	for (int vj = 0, vi = 0; vj < N; vj++) {
		int j = vlpd[vj].se;
		for (; vi < N && vlpd[vj].fi - vlmd[vi].fi > dia; vi++) {
			//add vi
			int i = vlmd[vi].se;
			fenlpd.update(i, L[i] + D[i]);
			//fendml.update(i, -vlmd[vi].fi);
			//debug("i = %d, j = %d. Distance = %lld\n", i, j, vlpd[vj].fi - vlmd[vi].fi);
			for (; qdmlind > i; qdmlind--) {
				qdml[qdmlind] = -vlmd[vi].fi;
				//debug("qdml[%d] = -vlmd[%d].fi = %lld\n", qdmlind, vi, -vlmd[vi].fi);
			}
		}


		//setmax(xmymn, (L[i] + D[i]) + (-L[j] + D[j]) - dia + C);
		//setmin(xmymx, (L[i] - D[i]) + (-L[j] - D[j]) + dia - C);
		//setmax(xpymn, (L[i] + D[i]) + (L[j] + D[j]) - dia + C);
		//setmin(xpymx, (L[i] - D[i]) + (L[j] - D[j]) + dia - C);
		ll qulpd = fenlpd.query(j);
		//ll qudml = fendml.query(j);
		ll qudml = qdml[j];
		if (qulpd != LLONG_MIN) {
			setmax(xmymn, qulpd + (-L[j] + D[j]) - dia + C);
			setmin(xmymx, -qudml + (-L[j] - D[j]) + dia - C);
			if (xmymn > xmymx) {
				return false;
			}

			setmax(xpymn, qulpd + (L[j] + D[j]) - dia + C);
			setmin(xpymx, -qudml + (L[j] - D[j]) + dia - C);
			if (xpymn > xpymx) {
				return false;
			}
		}
	}

	//debug("xmymn = %lld, xmymx = %lld. xpymn = %lld, xpymx = %lld.\n", xmymn, xmymx, xpymn, xpymx);
	//basic checks

	if (xmymn == LLONG_MIN) {
		return true;
	}

	int ubxmx = 0, lbxmn = 0;	//linear optimization...
	int nmoveu = 0, nmovel = 0;

	for (int j = 1; j < N; j++) {
		ll xmn = max(xpymn - L[j], xmymn + L[j]);
		ll xmx = min(xpymx - L[j], xmymx + L[j]);
		if (xmn > xmx) {
			continue;
		}

		/*
		if (upper_bound(L, L + j, xmx) != lower_bound(L, L + j, xmn)) {
			return true;
		}
		*/

		while (ubxmx < j && L[ubxmx] <= xmx) {
			ubxmx++;
			nmoveu++;
		}
		while (ubxmx > 0 && L[ubxmx - 1] > xmx) {
			ubxmx--;
			nmoveu++;
		}

		while (lbxmn < j && L[lbxmn] < xmn) {
			lbxmn++;
			nmovel++;
		}
		while (lbxmn > 0 && L[lbxmn - 1] >= xmn) {
			lbxmn--;
			nmovel++;
		}

		//check that it really is O(N)...
		assert(nmoveu <= 3 * N);
		assert(nmovel <= 3 * N);

		if (ubxmx != lbxmn) {
			return true;
		}
	}
	return false;
}

ll find_shortcut (int nnn, vector<int> lll, vector<int> ddd, int ccc) {
	//very very preliminary stuff - should also init other stuff
	N = nnn;
	C = ccc;
	L[0] = 0;
	for (int i = 1; i < N; i++) {
		L[i] = L[i - 1] + lll[i - 1];
	}
	for (int i = 0; i < N; i++) {
		D[i] = ddd[i];
	}

	//precomp here!
	for (int i = 0; i < N; i++) {
		vlmd[i] = make_pair(L[i] - D[i], i);
		vlpd[i] = make_pair(L[i] + D[i], i);
	}
	sort(vlmd, vlmd + N);
	sort(vlpd, vlpd + N);

	ll lo = 0, hi = (N + 1) * 1000000000ll;
	while (hi - lo > 1) {
		ll mid = (lo + hi) >> 1;
		if (moo(mid)) {
			hi = mid;
		} else {
			lo = mid;
		}
	}
	return hi;
}

• 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