백준 14636번 Money for Nothing

문제 요약

2차원 좌표계에서 크기가 M인 점의 집합 $P(p_i, d_i)$와 크기가 N인 점의 집합 $Q(q_j, e_j)$가 주어집니다.

P의 점을 왼쪽 아래로 하고, Q의 점을 오른쪽 위로 하는 직사각형 중에서 가장 큰 직사각형의 크기를 출력해야 합니다.

N,M은 최대 50만이고 좌표 범위는 1부터 $10^9$까지입니다.

풀이

문제가 요약한대로 위와 같은 상황이라는 것을 인지하고 할 수 있는 관찰이 하나 있습니다.

집합 P에서 절대 답의 후보가 될 수 없는 점들이 있습니다. P에 속하는 어떤 점 $A(p_A, d_A)$가 있다고 합시다. 만약 P에 속하는 다른 점 $B(p_B, d_B)$가 $p_B \le p_A$면서 $e_B \le e_A$라면 A는 절대 답의 후보가 될 수 없습니다.

이와 비슷한 논리를 집합 Q에 대해서도 적용이 가능합니다. 이러한 논리로 먼저 후보가 될 수 없는 점들을 P, Q에서 지워줍니다.

이러한 전처리가 끝난 집합들에 대해서 왼쪽 아래의 점들을 x좌표 순으로 $L_0, L_1, \cdots, L_{n-1}$, 오른쪽 위의 점들을 $U_0, U_1, \cdots, U_{m-1}$이라고 합시다.

각 $L_i$에 대해서 $L_i$를 왼쪽 아래 점으로 하는 직사각형 중에서 넓이가 가장 큰 직사각형의 넓이를 $S_i$라고 합시다. 우리가 원하는 답은 $max S_i$가 됩니다.

이를 나이브하게 찾으면 $O(NM)$으로 시간초과를 받습니다.

$L_i$와 연결해서 직사각형이 되는 $U_k$중에서 그 넓이가 $S_i$가 되는 $k$를 $opt_i$라고 부르겠습니다.

이 때, 아래와 같은 부등식이 성립합니다.
$$
\begin{gather}
S(i,j) = L_i랑 \text{ } U_j로 \text{만든 직사각형의 넓이} \\
let \quad i<j, k<l, \quad S(i,k) + S(j,l) > S(i,l) + S(j,k)
\end{gather}
$$
이것은 그림을 그려보면 바로 알 수 있다.

이걸로 $i<j$일 때, $opt_i \le opt_j$가 성립함을 알 수 있고 이를 통해서 분할정복으로 답을 구할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int N, M;
vector<pair<ll, ll>> P, C;
vector<pair<ll, ll>> L, U;
ll dp[500005];
ll mx;
void solve(int s, int e, int optl, int optr) {
    if (s > e) return;
    int mid = (s + e) >> 1;
    int opt = optl;
    ll& ans = dp[mid];
    ans = -2e18;
    for (int i = optl; i <= optr; ++i) {
        ll dt = U[i].second - L[mid].second;
        ll dp = U[i].first - L[mid].first;
        if (dt >= 0 || dp >= 0) {
            ll val = dt * dp;
            if (ans <= val) {
                ans = val; opt = i;
            }
        }
    }
    solve(s, mid - 1, optl, opt);
    solve(mid + 1, e, opt, optr);
    mx = max(mx, ans);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> M >> N; P.resize(M); C.resize(N);
    for (int i = 0; i < M; ++i) cin >> P[i].first >> P[i].second;
    for (int i = 0; i < N; ++i) cin >> C[i].first >> C[i].second;
    sort(P.begin(), P.end());
    sort(C.begin(), C.end());
    for (int i = 0; i < M; ++i) {
        if(L.empty() || L.back().second > P[i].second) L.push_back(P[i]);
    }
    for (int i = 0; i < N; ++i) {
        while (!U.empty() && U.back().second <= C[i].second) U.pop_back();
        U.push_back(C[i]);
    }
    // memset(dp, -1, sizeof(dp));
    for (int i = 0; i < L.size() - 1; ++i) assert(L[i].first < L[i + 1].first && L[i].second > L[i + 1].second);
    for (int i = 0; i < U.size() - 1; ++i) assert(U[i].first < U[i + 1].first && U[i].second > U[i + 1].second);
    solve(0, L.size() - 1, 0, U.size() - 1);
    assert(mx >= 0);
    cout << mx << '\n';
    return 0;
}