CF1408D Searchlights
注意到所有海盗有三种方式摆脱所有探照灯的控制：
1、一直向上走
2、一直向右走
3、向上走到某点后一直向右走
前两种比较好处理。对于第 \(3\) 种，不难发现只有当全局中点在灯的边界线上才会影响答案（但可能不走到边界线上更优）。这样的边界线最多 \(2000\) 条，所以我们可以先处理出每个海盗到每条边界线的距离 \(d\)，将其走到此处还需要向右走才能走出去的步数记为 \(f_d\)。设当前向上走了 \(i\) 步，则答案就是 \(\min (i + \max f_i)\)。
注意倒着扫描边界线并且先更新 \(f_d\)，这样才能包括未走到边界线上的情况。最后更新答案。
时间复杂度为 \(O(nm)\)，
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l); i <= (r); ++ i)
#define G(i,r,l) for(int i(r); i >= (l); -- i)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 3000;
const int MAXN = 1e6;
int f[1005000];
int n, m, mx, ans = 0, nw;
int a[N], b[N], c[N], d[N];
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;F(i, 1, n) cin >> a[i] >> b[i];F(i, 1, m) cin >> c[i] >> d[i];F(i, 1, n){F(j, 1, m){if(a[i] <= c[j] && b[i] <= d[j]){mx = max(mx, d[j] - b[i]);f[d[j] - b[i]] = max(f[d[j] - b[i]], c[j] - a[i] + 1);}}}ans = mx + 1;
// cout << ans << '\n'; G(i, mx, 0){nw = max(nw, f[i]);ans = min(ans, nw + i);}cout << ans << '\n';return fflush(0), 0;
}