代码

#include <bits/stdc++.h>
using namespace std;
#define clr(a) memset(a, 0, sizeof(a))
#define full(a) memset(a, 0x3f, sizeof(a))
#define mset(a, b) memset(a, b, sizeof(a))
#define cpy(a,b) memcpy(a, b, sizeof(a))
#define fornext(x, i) for(signed i = hd[x], y = ver[i]; i; i = nxt[i], y = ver[i])
#define Rep(i, a, b) for(signed i = (signed)(a); i <= (signed)(b); ++i)
#define dRep(i, a, b) for(signed i = (signed)(a); i >= (signed)(b); --i)
#define ioset(a) freopen(a".in", "r", stdin), freopen(a".out", "wx", stdout);
#define pb push_back
#define It iterator
#define endl '\n'
#define un unsigned
#define int ll
#define ll long long
#define db double
#define rept cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
#define dbg cerr<<"c "
#define dbug(x) cerr << #x " = " << (x) << endl
template<typename _T> inline void rd(_T &_d) {
	signed _f; char _c; _f = 1, _d = 0; while (_c = getchar(), !isdigit(_c)) if (_c == '-') _f = -1;
	while (isdigit(_c)) _d = _d * 10 + _c - '0', _c = getchar();
	_d = _f * _d;
}

// template<typename _T> inline void _prt(_T _d) { cerr << _d << ' '; }
// template <typename _T, typename ...Args> inline void _prt(_T _d, Args ..._a) { _prt(_d), _prt(_a...); }
// template <typename _T, typename ...Args> inline void prt(_T _d, Args ..._a) { _prt(_d), _prt(_a...), cerr << endl; }
// template <typename _T, typename ...Args> inline void prt(_T _d) { cerr << _d << endl; }


const int N = 5e5 + 50005;
#define ls (x<<1)
#define rs ((x<<1)|1)
signed n, m, wx, wy, a[N], b[N], x[N], y[N], t, vl[N];
int add[N * 4], mn[N * 4];
vector<signed> v[N];

void sprd(int x) {
	if (!add[x]) return;
	add[ls] += add[x], add[rs] += add[x], mn[ls] += add[x], mn[rs] += add[x];
	add[x] = 0;
}

void modi(int x, int l, int r, int qr, int v) {
	if (r <= qr) {
		add[x] += v, mn[x] += v; return;
	}
	sprd(x);
	int mid = (l + r) >> 1;
	modi(ls, l, mid, qr, v);
	if (qr > mid) modi(rs, mid + 1, r, qr, v);
	mn[x] = min(mn[ls], mn[rs]);
}

void rst(int x, int l, int r) {
	if (l == r) return add[x] = mn[x] = 0, void(0);
	int mid = (l + r) >> 1;
	rst(ls, l, mid);
	rst(rs, mid + 1, r);
	mn[x] = add[x] = 0;
}

bool chk(int val) {
	rst(1, 1, wx);
	int pt = m, sum = 0;
	Rep(i, 1, n) if (a[i] > 0) modi(1, 1, wx, a[i] - 1, val);
	dRep(i, wy, 1) {
		for (int j = 0; j < v[i].size(); ++j) modi(1, 1, wx, v[i][j], -1);
		if (sum + mn[1] < 0) return 0;
		while (pt && b[pt] >= i) sum += val, --pt;
	}
	return 1;
}

signed main() {
	// ioset("clear");
	n = m = 50000, t = 5e5;
	Rep(i, 1, n) a[i] = i + 1e5;
	Rep(i, 1, m) b[i] = 1e9 - i;
	Rep(i, 1, t) x[i] = i, y[i] = 1e6 - i;

	Rep(i, 1, n) vl[i] = a[i];
	Rep(i, 1, t) vl[n + i] = x[i];
	sort(vl + 1, vl + t + n + 1);
	wx = unique(vl + 1, vl + t + n + 1) - vl - 1;
	Rep(i, 1, n) a[i] = lower_bound(vl + 1, vl + wx + 1, a[i]) - vl;
	Rep(i, 1, t) x[i] = lower_bound(vl + 1, vl + wx + 1, x[i]) - vl;

	Rep(i, 1, m) vl[i] = b[i];
	Rep(i, 1, t) vl[m + i] = y[i];
	sort(vl + 1, vl + t + m + 1);
	wy = unique(vl + 1, vl + t + m + 1) - vl - 1;
	Rep(i, 1, m) b[i] = lower_bound(vl + 1, vl + wy + 1, b[i]) - vl;
	Rep(i, 1, t) y[i] = lower_bound(vl + 1, vl + wy + 1, y[i]) - vl;

	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	Rep(i, 1, t) v[y[i]].pb(x[i]);

	int l = 1, r = t, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (chk(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
	return 0;
}
/*	Rep(i, 1, wx) Rep(j, 1, wy) {
		tmp = sum = 0;
		Rep(k, 1, t) if (x[k] >= i && y[k] >= j) ++tmp;
		Rep(k, 1, n) if (a[k] > i) ++sum;
		Rep(k, 1, m) if (b[k] > j) ++sum;
		ans = max(ans, (int)ceil(1.0 * tmp / sum));
	}
*/

评测结果