백준26608 캠핑하기

작성일 | In

문제 링크

  • http://icpc.me/26608

사용 알고리즘

  • CHT

시간복잡도

  • $O((N+M) \log X)$

풀이

모든 $x$에 대해 $\frac{B_i-kx}{A_i+kx}$의 최댓값을 구해야 합니다. $\frac{B_i-kx}{A_i+kx} = \frac{A_i+B_i}{A_i+kx}-1$이고, 이 식을 최대화하는 것은 $\frac{kx+A_i}{A_i+B_i}$를 최소화하는 것과 동치입니다.
일차 함수가 여러 개 있을 때, 특정 $x$좌표에서의 최솟값을 구하는 방법은 Convex Hull Trick이라는 이름으로 잘 알려져 있습니다. Li-Chao Tree를 사용하면 $O((N+M) \log X)$ 시간에 해결할 수 있습니다.

전체 코드

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
110
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<typename T>
int Sign(T x){ return (x > T(0)) - (x < T(0)); }
struct Fraction{
    ll p, q;
    Fraction() : Fraction(0, 1) {}
    Fraction(ll v) : Fraction(v, 1) {}
    Fraction(ll p, ll q) : p(p), q(q) { norm(); }
    void norm(){
        if(q == 0){ p = (p > 0) - (p < 0); return; }
        auto g = __gcd(p, q);
        p /= g; q /= g;
        if(q < 0) p *= -1, q *= -1;
    }
    bool operator < (const Fraction &t) const {
        if(*this == t) return false;
        if(p == -1 && q == 0) return true;
        if(t.p == +1 && t.q == 0) return true;
        if(p == +1 && q == 0) return false;
        if(t.p == -1 && t.q == 0) return false;
        return p * t.q < t.p * q;
    }
    bool operator > (const Fraction &t) const { return *this != t && t < *this; }
    bool operator <= (const Fraction &t) const { return *this == t || *this < t; }
    bool operator >= (const Fraction &t) const { return *this == t || *this > t; }
    bool operator == (const Fraction &t) const { return q != 0 ? t.q != 0 && p * t.q == t.p * q : t.q == 0 && Sign(p) == Sign(t.p); }
    bool operator != (const Fraction &t) const { return !(*this == t); }
    Fraction& operator += (const Fraction &t) {
        p = t.q * p + q * t.p; q = q * t.q;
        norm(); return *this;
    }
    Fraction& operator -= (const Fraction &t) {
        p = t.q * p - q * t.p; q = q * t.q;
        norm(); return *this;
    }
    Fraction& operator *= (const Fraction &t) {
        p *= t.p; q *= t.q;
        norm(); return *this;
    }
    Fraction& operator /= (const Fraction &t) {
        p *= t.q; q *= t.p;
        norm(); return *this;
    }
    Fraction operator + (const Fraction &t) const { return Fraction(*this) += t; }
    Fraction operator - (const Fraction &t) const { return Fraction(*this) -= t; }
    Fraction operator * (const Fraction &t) const { return Fraction(*this) *= t; }
    Fraction operator / (const Fraction &t) const { return Fraction(*this) /= t; }
    Fraction operator - () const { return Fraction(-p, q); }
};

struct Line{
    Fraction a, b;
    Line() : Line(0, Fraction(1, 0)) {}
    Line(Fraction a, Fraction b) : a(a), b(b) {}
    Fraction f(Fraction x) const { return a * x + b; }
};

struct LiChaoTree{
    static constexpr int RANGE = 1 << 17;
    struct Node{
        int l, r; Line v;
        Node() : l(-1), r(-1), v() {}
    };
    vector<Node> T;
    LiChaoTree(){ clear(); }
    void clear(){ T.clear(); T.emplace_back(); }
    void update(Line v, int node=0, int s=0, int e=RANGE-1){
        Line lo = T[node].v, hi = v;
        if(lo.f(s) > hi.f(s)) swap(lo, hi);
        if(lo.f(e) <= hi.f(e)){ T[node].v = lo; return; }
        int m = (s + e) / 2;
        if(lo.f(m) < hi.f(m)){
            T[node].v = lo;
            if(T[node].r == -1) T[node].r = T.size(), T.emplace_back();
            update(hi, T[node].r, m+1, e);
        }
        else{
            T[node].v = hi;
            if(T[node].l == -1) T[node].l = T.size(), T.emplace_back();
            update(lo, T[node].l, s, m);
        }
    }
    void add(Fraction a, Fraction b){ update(Line(a, b)); }
    Fraction query(ll x, int node=0, int s=0, int e=RANGE-1) const {
        Fraction res = node != -1 ? T[node].v.f(x) : Fraction(1, 0);
        if(node == -1 || s == e) return res;
        int m = (s + e) / 2;
        if(x <= m) res = min(res, query(x, T[node].l, s, m));
        else res = min(res, query(x, T[node].r, m+1, e));
        return res;
    }
};

ll N, M, K, A[303030], B[303030];
LiChaoTree T;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K;
    for(int i=1; i<=N; i++) cin >> A[i] >> B[i];
    for(int i=1; i<=N; i++) T.add(Fraction(K, A[i]+B[i]), Fraction(A[i], A[i]+B[i]));
    for(int i=1; i<=M; i++){
        auto res = T.query(i); res = Fraction(1) / res - 1;
        if(res.p == 0) cout << "0/0" << "\n";
        else cout << res.p << "/" << res.q << "\n";
    }
}