백준17526 Star Trec

작성일 | In

문제 링크

  • http://icpc.me/17526

문제 출처

  • 2019 서울 리저널 인터넷 예선 J번

사용 알고리즘

  • Li-Chao Tree

시간복잡도

  • O(NlgN)

풀이

wait[i] = i번째 우주선을 갈아타는 데 걸리는 시간, speed[i] = i번째 우주선의 속도, dist[i] = 시작점부터 i번째 지점까지의 거리
라고 정의합시다.

먼저, 첫 번째 우주선을 타고 시작점에서 x까지 가는 데 걸리는 시간 f_1(x) = speed[1] * x + wait[1]입니다.
각 지점마다 우주선을 갈아탈 수 있기 때문에, 갈아타는 경우도 고려를 해줘야 합니다.
당연히 우주선을 갈아타더라도 f_i(x)는 기울기가 speed인 일차함수로 나타낼 수 있습니다.

i번 지점까지 가는 데 now만큼의 시간이 걸렸다고 합시다. i번 지점에서 우주선을 갈아타는 경우를 생각해보면
기울기는 당연히 speed[i]이고, y절편은 wait[i] + now - speed[i] * dist[i]인 직선으로 나타낼 수 있습니다.

결국 이 문제는 f_i(x) = speed[i] * x + wait[i] + now - speed[i] * dist[i] 형태로 나타낼 수 있는 n개의 일차함수에서 특정 지점의 최솟값을 여러 번 구하는 문제로 바뀌게 되고, 이는 li-chao tree를 이용해 쉽게 구할 수 있습니다.

전체 코드

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
111
112
113
114
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define pb push_back
using namespace std;
//using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int di[] = {1, 0, -1, 0, 1, 1, -1, -1}, dj[] = {0, 1, 0, -1, 1, -1, 1, -1};
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  ll g = a; x = 1, y = 0;
  if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  return g;
}
ll inv(ll a, ll m){ //return x when ax mod m = 1, fail -> -1
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}
void finish(){ exit(0); }

const ll inf = 1e16;

struct Line{
    ll a, b;
    ll get(ll x){
        return a * x + b;
    }
};

struct Node{
    int l, r; //child
    ll s, e; //range
    Line line;
};

struct LiChao{
    vector<Node> tree;

    void init(ll s, ll e){
        tree.push_back({-1, -1, s, e, {0, inf}});
    }

    void insert(Line v, int node = 0){
        ll s = tree[node].s, e = tree[node].e;
        ll m = s + e >> 1;
        Line low = tree[node].line, high = v;
        if(low.get(s) > high.get(s)) swap(low, high);
        if(low.get(e) <= high.get(e)){
            tree[node].line = low; return;
        }
        if(low.get(m) <= high.get(m)){
            tree[node].line = low;
            if(tree[node].r == -1){
                tree[node].r = tree.size();
                tree.push_back({-1, -1, m+1, e, {0, inf}});
            }
            insert(high, tree[node].r);
        }else{
            tree[node].line = high;
            if(tree[node].l == -1){
                tree[node].l = tree.size();
                tree.push_back({-1, -1, s, m, {0, inf}});
            }
            insert(low, tree[node].l);
        }
    }

    ll get(ll x, int node = 0){
        if(node == -1) return inf;
        ll s = tree[node].s, e = tree[node].e;
        ll m = s + e >> 1;
        if(x <= m) return min(tree[node].line.get(x), get(x, tree[node].l));
        else return min(tree[node].line.get(x), get(x, tree[node].r));
    }
}seg;

ll wait[101010], speed[101010];
ll sum[101010];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=2; i<=n; i++){
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    for(int i=1; i<n; i++){
        cin >> wait[i] >> speed[i];
    }

    seg.init(0, 1e9+7);
    seg.insert({speed[1], wait[1]});
    for(int i=2; i<n; i++){
        ll now = seg.get(sum[i]);
        ll bias = wait[i] + now - speed[i] * sum[i];
        seg.insert({speed[i], bias});
    }
    cout << seg.get(sum[n]);
}