[Algorithm] cpp 백준 14636번: Money for Nothing

문제

링크: https://www.acmicpc.net/problem/14636
요약: 하나의 생산자 회사와 하나의 소비자 회사를 골라, 생산 시작일 d 이후부터 소비자 마감 다음날 e 전까지(즉 e > d), 하루 1개씩 공급하여 총 이익 (e - d) * (q - p)를 최대화합니다. 여기서 p는 생산 단가, q는 소비 단가이며 q > p여야 계약이 유효합니다. 유효한 쌍이 없으면 0을 출력합니다. 제약: \(1 \le m,n \le 5\times 10^5\), 값들은 \(\le 10^9\).

입력/출력

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
<입력>
m n
p1 d1
...
pm dm
q1 e1
...
qn en

<출력>
최대 가능한 총 이익 (없으면 0)

접근 개요

핵심 관찰: 수익은 (e - d) * (q - p). 따라서 d가 작을수록, p가 낮을수록, e가 클수록, q가 높을수록 유리합니다. 동일 날짜에서 더 비싼 p는 지배되며, 동일 날짜에서 더 낮은 q는 지배됩니다.
비지배 전처리(파레토 경계):
- 생산자 (d, p): d 오름차순으로 정렬 후 같은 날짜는 p 최소만 남기고, d가 증가할수록 p가 엄격히 감소하도록 필터링(오른쪽으로 갈수록 더 싸짐)합니다.
- 소비자 (e, q): e 오름차순 정렬 후 같은 날짜는 q 최대만 남기고, 뒤에서부터 스윕하여 e가 증가할수록 q가 엄격히 증가하도록 필터링(오른쪽으로 갈수록 더 비쌈)합니다.
이후 남는 두 단조 수열 D[i](증가), P[i](감소), E[j](증가), Q[j](증가)에서 E[j] > D[i] 및 Q[j] > P[i]일 때만 (E[j]-D[i])*(Q[j]-P[i]) 후보가 됩니다.
점수 행렬 Score[i][j] = (E[j]-D[i])*(Q[j]-P[i])는 완전단조 성질(행별 최적 j*가 단조)로 분할정복 최적화가 가능합니다. 이를 이용해 전체 최대값을 효율적으로 탐색합니다.

flowchart TB
  A[입력 m,n 및 (p,d),(q,e)] --> B[정렬·중복축약]
  B --> C[비지배 전처리로 파레토 경계 구축]
  C --> D[단조 수열 D,P,E,Q 확보]
  D --> E[분할정복 최적화로 행별 최적 열 j* 탐색]
  E --> F[유효쌍만 고려하여 최대 수익 계산]

알고리즘

생산자 처리: d 오름차순 정렬 → 같은 d는 p 최솟값만 유지 → 왼→오로 스윕하며 p가 더 작을 때만 남김.
소비자 처리: e 오름차순 정렬 → 같은 e는 q 최댓값만 유지 → 오른→왼으로 스윕하며 q가 증가할 때만 남김(역순 뒤집기).
분할정복 최적화(DnC): 중간 행 im에 대해 열 구간 [jl..jr]에서 최적 열 bestJ를 찾고, 좌/우 재귀에 각각 [jl..bestJ], [bestJ..jr]로 탐색 구간을 좁혀가며 전역 최대를 갱신합니다. 실제 정답 갱신 시에는 E[j] > D[i], Q[j] > P[i]만 인정합니다.
안전성: 곱 중간값은 ~(2e9)*(2e9) 가능하므로 __int128으로 계산, 최종 출력은 64비트로 캐스팅. 유효쌍이 없으면 0.

복잡도

시간: 정렬 및 전처리 O((m+n) log(m+n)), 분할정복 탐색 O(I log J)~O(I + J) 수준(실무에서는 선형에 가깝게 동작). 전체 대략 O((m+n) log(m+n)).
공간: 입력과 전처리 벡터 O(m+n).

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i128 = __int128_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;

    vector<pair<int64,int64>> rawProd; rawProd.reserve(m); // (d, p)
    for (int i = 0; i < m; ++i) {
        int64 p, d; cin >> p >> d;
        rawProd.emplace_back(d, p);
    }

    vector<pair<int64,int64>> rawCons; rawCons.reserve(n); // (e, q)
    for (int j = 0; j < n; ++j) {
        int64 q, e; cin >> q >> e;
        rawCons.emplace_back(e, q);
    }

    // Producers: sort by d asc, keep minimal p per d, then keep non-dominated (p strictly decreasing as d increases)
    sort(rawProd.begin(), rawProd.end()); // by d, then p
    vector<pair<int64,int64>> prodByD; prodByD.reserve(rawProd.size());
    for (size_t i = 0; i < rawProd.size(); ) {
        int64 d = rawProd[i].first;
        int64 minp = rawProd[i].second;
        size_t j = i + 1;
        while (j < rawProd.size() && rawProd[j].first == d) {
            minp = min(minp, rawProd[j].second);
            ++j;
        }
        prodByD.emplace_back(d, minp);
        i = j;
    }
    vector<pair<int64,int64>> P; P.reserve(prodByD.size());
    for (auto &pp : prodByD) {
        if (P.empty() || pp.second < P.back().second) P.push_back(pp);
    }
    if (P.empty()) { cout << 0 << '\n'; return 0; }

    // Consumers: sort by e asc, keep maximal q per e, then keep non-dominated maxima (q strictly increasing as e increases after reverse pass)
    sort(rawCons.begin(), rawCons.end()); // by e, then q
    vector<pair<int64,int64>> consByE; consByE.reserve(rawCons.size());
    for (size_t i = 0; i < rawCons.size(); ) {
        int64 e = rawCons[i].first;
        int64 maxq = rawCons[i].second;
        size_t j = i + 1;
        while (j < rawCons.size() && rawCons[j].first == e) {
            maxq = max(maxq, rawCons[j].second);
            ++j;
        }
        consByE.emplace_back(e, maxq);
        i = j;
    }
    // Build consumers frontier with q strictly increasing as e increases.
    // On ties of q, keep the later (larger e) point.
    vector<pair<int64,int64>> C; C.reserve(consByE.size());
    for (const auto &eq : consByE) {
        if (C.empty() || eq.second > C.back().second) {
            C.push_back(eq);
        } else if (eq.second == C.back().second) {
            C.back().first = eq.first; // keep larger e for the same q
        }
    }
    if (C.empty()) { cout << 0 << '\n'; return 0; }

    const int I = (int)P.size();
    const int J = (int)C.size();

    vector<int64> D(I), PP(I), E(J), Q(J);
    for (int i = 0; i < I; ++i) { D[i] = P[i].first; PP[i] = P[i].second; }
    for (int j = 0; j < J; ++j) { E[j] = C[j].first; Q[j] = C[j].second; }

    auto solve = [&](auto&& self, int il, int ir, int jl, int jr, int64 &answer) -> void {
        if (il > ir || jl > jr) return;
        int im = (il + ir) >> 1;

        i128 bestScore = (i128)LLONG_MIN;
        int bestJ = jl;

        for (int j = jl; j <= jr; ++j) {
            // For divide-and-conquer splitting (Monge), use raw score (can be negative)
            i128 sc = (i128)(E[j] - D[im]) * (i128)(Q[j] - PP[im]);
            if (sc > bestScore) {
                bestScore = sc;
                bestJ = j;
            }
            // For actual profit, only count valid contracts: e > d and q > p
            if (E[j] > D[im] && Q[j] > PP[im]) {
                i128 prof = (i128)(E[j] - D[im]) * (i128)(Q[j] - PP[im]);
                if (prof > (i128)answer) answer = (int64)prof;
            }
        }

        self(self, il, im - 1, jl, bestJ, answer);
        self(self, im + 1, ir, bestJ, jr, answer);
    };

    int64 ans = 0;
    solve(solve, 0, I - 1, 0, J - 1, ans);
    cout << ans << '\n';
    return 0;
}