题目大意

有 $n$ 个点，它们的位置分别在 $x_i$ ，它们有值 $a_i$ 。现在给 $T$ 秒钟时间，要求选定的一个 $i$ 从它出发，在这 $T$ 秒内可以花 $1$ 秒时间移动， $0$ 秒时间拿取某个点的 $1$ （ $a_j\leftarrow a_j-1$ ）、放在某个点（ $a_j\leftarrow a_j+1$ ）并且手里最多只有 $1$ ，求选择的点 $i$ 在 $T$ 秒后最大能有多少。

$n\le5\times10^5,T\le10^{18}$ 。

题解

即求每个点前 $k$ 近的左右端点。用单调队列的思想做。

代码

const int N = 5e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	ll m;
	ll x[N], a[N];
	ll sum[N];
	bool check(ll mid) {
		int l = 1, r = n + 1, lx = 0, rx = 0;
		ll t = 0, tot = 0;
		for (int i = 1; i <= n; i++)
			if (tot + a[i] <= mid) {
				tot += a[i];
				t += 1ll * (x[i] - x[1]) * a[i];
			} else {
				r = i;
				rx = mid - tot;
				t += 1ll * (x[i] - x[1]) * rx;
				break;
			}
		if (t <= m) return 1;
		for (int i = 2; i <= n; i++) {
			t -= (sum[r - 1] - sum[i - 1] + rx) * (x[i] - x[i-1]);
			t += (sum[i - 1] - sum[l - 1] - lx) * (x[i] - x[i-1]);
			while (r <= n && x[r] - x[i] <= x[i] - x[l]) {
				int g = min(a[l] - lx, a[r] - rx);
				lx += g, rx += g;
				t += ((x[r] - x[i]) - (x[i] - x[l])) * g;

				if (a[l] == lx) lx = 0, l++;
				if (a[r] == rx) rx = 0, r++;
			}
			if (t <= m) return 1;
		}
		return 0;
	}
	int main () {
		n = Read(), m = Read() / 2;
		for (int i = 1; i <= n; i++) x[i] = Read();
		for (int i = 1; i <= n; i++) { 
			a[i] = Read();
		   	sum[i] = a[i] + sum[i - 1]; 
		}
		sum[n + 1] = sum[n] + 1145141919;
		ll l = 1, r = sum[n], ans;
		while (l <= r) {
			ll mid = (l + r) >> 1;
			if (check(mid)) l = (ans = mid) + 1;
			else r = mid - 1;
		}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
	freopen("block.in", "r", stdin);
	freopen("block.out", "w", stdout);
	Main::main();
	return 0;
}