VOJ - BGMINE

Source: BGMINE
Tags: Data Structures

Problem:
Trên một con đường biểu diễn như trục số thực có N mỏ vàng đánh số từ 1 đến N. Mỏ thứ i nằm ở tọa độ X[i], có tổng trữ lượng vàng là G[i], trong mỏ còn có lượng đá đủ để xây dựng đoạn kè có độ dài R[i]. Trong mùa mưa lũ, việc phòng chống ngập cho các mỏ trở nên cấp thiết và rất khó khăn trong việc vận chuyển vật liệu xây kè. Vì vậy, Chính phủ muốn dùng đá ở một dãy mỏ liên tiếp để xây dựng một đoạn kè liên tục bảo vệ tất cả các mỏ đó. Ta có thể coi cửa các mỏ vàng rất nhỏ, nên dù chỉ nằm ở đầu đoạn kè thì mỏ vẫn được an toàn.
Hãy giúp Chính phủ xác định đoạn kè có thể xây dựng với tổng trữ lượng vàng trong các mỏ được bảo vệ là lớn nhất.
N ≤ 1e5.
-1e9 ≤ X[1] < X[2] < ... < X[N] ≤ 1e9.
0 ≤ G[i], R[i] ≤ 1e9.

Ví dụ:
Input
4
0 5 1
1 7 2
4 4 1
7 15 1

Output:
16

Explanation:
Xây dựng đoạn kè độ dài 4 từ tọa độ 0 đến tọa độ 4 để bảo vệ các mỏ 1, 2, 3, tổng trữ lượng vàng trong các mỏ là 5 + 7 + 4 = 16.

Solution:
Tại mỏ vàng thứ i, ta sẽ tìm mỏ vàng j xa nhất mà tổng R[j] + R[j + 1] + ... + R[i] ≥ X[i] - X[j].
Ý này chắc nhiều bạn cũng nghĩ ra và đi theo hướng 2 pointers hoặc binary search, nhưng đáng tiếc một điều là mỏ thứ j thỏa chưa chắc mỏ thứ j + 1 thỏa. Nếu đã code cách này và nộp lên thì sẽ được 85 điểm. Vậy tại sao lại như thế?
Thử ví dụ sau đây:
10
1 1 0
2 1 0
3 1 5
4 1 0
5 1 0
6 1 0
7 1 0
8 1 0
9 1 0
10 1 4
Bạn ra bao nhiêu? Nếu bạn ra 5 hoặc thậm chí chỉ ra 1, thì xin chia buồn bạn, đáp án đúng là 10.
Gọi SumR[i] là tổng số lượng đá từ mỏ 1 đến mỏ i, với mỗi đoạn (j, i), ta có điều kiện sau:
SumR[i] - SumR[j - 1] ≥ X[i] - X[j]
<=> SumR[i] - X[i] ≥ SumR[j - 1] - X[j]
Ta tiến hành xây dựng một cây IT hoặc BIT lưu min các giá trị G[j] theo SumR[j - 1] - X[j]. Nhớ là giá trị SumR[j - 1] - X[j] có thể rất lớn nên cần phải nén số lại.
Độ phức tạp O(NlogN)

Code:
#include <iostream>
#include <algorithm>

using namespace std;

int n, x[100015];
long long g[100015], r[100015], f[100015], BIT[100015], res;

void update(int x, long long v) {
    for (; x <= n + 1; x += x & -x)
        BIT[x] = min(BIT[x], v);
}

long long get(int x) {
    long long res = 1e18;
    for (; x; x -= x & -x)
        res = min(res, BIT[x]);
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> g[i] >> r[i],
        g[i] += g[i - 1],
        r[i] += r[i - 1];
    for (int i = 0; i < n; i++)
        f[i] = r[i] - x[i + 1];
    sort(f, f + n);
    for (int i = 1; i <= n + 1; i++)
        BIT[i] = 1e18;
    for (int i = 1; i <= n; i++)
        update(lower_bound(f, f + n, r[i - 1] - x[i]) - f + 1, g[i - 1]),
        res = max(res, g[i] - get(upper_bound(f, f + n, r[i] - x[i]) - f));
    cout << res;

}