Submission #1837143

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cassert>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 3e5 + 7;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int W, H, C, n, ans;

struct pt {
	int x, y;
	inline bool operator < (const pt &v) const { return x < v.x; }
}d[maxN];

inline bool in(const pt &x, const pt &y) {
	return y.x <= x.x && x.y <= y.y;
}

inline int calc(const pt &x, const pt &y, const pt &l, const pt &r) {
	return y.x - x.x + min(l.y, r.y) - max(l.x, r.x);
}

void solve(int l, int r) {
	if (l >= r) return;	
	static pt a[maxN];
	static deque<pt> q;
	int mid = (l + r) >> 1;
	solve(l, mid);
	solve(mid+1, r);

	for (int up = H, dw = 0, i = mid; i >= l; -- i) {
		a[i] = (pt){dw, up};
		if (d[i].y >= C) up = min(up, d[i].y);
		if (d[i].y <= C) dw = max(dw, d[i].y); 
	}

	for (int up = H, dw = 0, i = mid+1; i <= r; ++ i) {
		a[i] = (pt){dw, up};
		if (d[i].y >= C) up = min(up, d[i].y);
		if (d[i].y <= C) dw = max(dw, d[i].y);
	}

	for (int i = l, j = r; i <= mid; ++ i) {
		for (; j > mid && !in(a[i], a[j]); -- j);
		if (in(a[i], a[j])) ans = max(ans, calc(d[i], d[j], a[i], a[j])); else break;
	}

	for (int i = r, j = l; i > mid; -- i) {
		for (; j <= mid && !in(a[i], a[j]); ++ j);
		if (in(a[i], a[j])) ans = max(ans, calc(d[i], d[j], a[i], a[j])); else break;
	}

#define eval(v) ((v).x + (v).y)
	while (!q.empty()) q.pop_back();
	for (int i = mid, j = mid+1; i >= l; -- i) {
		for (; j <= r && a[j].x <= a[i].x; ++ j) {
			pt nw = (pt){d[j].x, a[j].y};
			while (!q.empty() && eval(q.back()) <= eval(nw)) q.pop_back();
			q.push_back(nw);
		}
		while (!q.empty() && q.front().y > a[i].y) q.pop_front();
		if (!q.empty()) ans = max(ans, eval(q.front()) - d[i].x - a[i].x);
	}
#undef eval
#define eval(v) ((v).y - (v).x)
	while (!q.empty()) q.pop_back();
	for (int i = mid + 1, j = mid; i <= r; ++ i) {
		for (; j >= l && a[j].x <= a[i].x; -- j) {
			pt nw = (pt){d[j].x, a[j].y};
			while (!q.empty() && eval(q.back()) <= eval(nw)) q.pop_back();
			q.push_back(nw);
		}
		while (!q.empty() && q.front().y > a[i].y) q.pop_front();
		if (!q.empty()) ans = max(ans, eval(q.front()) + d[i].x - a[i].x);
	}
#undef eval
}

int main() {

	W = ri(), H = ri(), n = ri();
	rep (i, 1, n) d[i].x = ri(), d[i].y = ri();
	ans = max(W, H) + 1;

	sort(d+1, d+n+1); C = H / 2;
	d[0] = (pt){0, C}, d[n+1] = (pt){W, C};
	ans = max(ans, d[1].x + H);
	ans = max(ans, W - d[n].x + H);
	solve(0, n+1);

	rep (i, 1, n) swap(d[i].x, d[i].y); swap(H, W);
	sort(d+1, d+n+1); C = H / 2;
	d[0] = (pt){0, C}, d[n+1] = (pt){W, C};
	ans = max(ans, d[1].x + H);
	ans = max(ans, W - d[n].x + H);
	solve(0, n+1);

	printf("%d\n", ans << 1);

	return 0;
}

Submission Info

Judge Result