Submission #1222885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222885		minhpk	Two Antennas (JOI19_antennas)	C++20	22 / 100	350 ms	72224 KiB

antennas

#include <iostream>
#include <vector>
#include <algorithm>

// Sử dụng 'using' cho kiểu dữ liệu long long, là một cách làm tốt hơn #define.
using ll = long long;
using namespace std;

// --- Hằng số với tên gọi rõ ràng ---
const int MAX_N = 1000005;      // Kích thước tối đa cho các mảng
const int SEG_TREE_SIZE = MAX_N * 4; // Kích thước cây phân đoạn
const ll INF = 4e18; // Giá trị lớn tượng trưng cho vô cực, đủ lớn để tránh tràn số

// --- Các cấu trúc dữ liệu với tên rõ ràng ---
// Lưu trữ thông tin cho mỗi item
struct Item {
    ll height, min_dist, max_dist;
};

// Lưu trữ thông tin cho mỗi truy vấn
struct Query {
    int l, r, id;
};

// --- Biến toàn cục ---
int num_items, num_queries;
Item items[MAX_N];
Query queries[MAX_N];
ll results[MAX_N];

// Mảng vector để xử lý sự kiện trong thuật toán Sweep-line
// start_events[i] chứa các item 'bắt đầu' có hiệu lực tại vị trí i
// end_events[i] chứa các item 'kết thúc' hiệu lực tại vị trí i
vector<int> start_events[MAX_N];
vector<int> end_events[MAX_N];

// --- Cây phân đoạn (Segment Tree) ---
// Cây phân đoạn được thiết kế đặc biệt để giải quyết bài toán này.
// Mỗi nút trong cây lưu trữ:
// 1. min_h_tree: giá trị min(h_i) trong đoạn [l, r] của nút.
// 2. max_diff_tree: giá trị max(h_j - h_i) đã tìm được trong đoạn [l, r].
// 3. lazy_tree: giá trị h_j được truyền xuống một cách lười biếng.
ll min_h_tree[SEG_TREE_SIZE];
ll max_diff_tree[SEG_TREE_SIZE];
ll lazy_tree[SEG_TREE_SIZE];

// Hàm so sánh để sắp xếp các truy vấn theo điểm cuối bên phải (r)
bool compare_queries(const Query& A, const Query& B) {
    return A.r < B.r;
}

// Đẩy giá trị lazy xuống các nút con
void push_down(int id) {
    if (lazy_tree[id] != -INF) {
        // Cập nhật kết quả của nút hiện tại dựa trên giá trị lazy
        // Đây là bước cốt lõi: max_diff = max(max_diff, h_j - min(h_i))
        max_diff_tree[id] = max(max_diff_tree[id], lazy_tree[id] - min_h_tree[id]);

        // Truyền giá trị lazy xuống các nút con
        int lc = id << 1, rc = lc | 1;
        lazy_tree[lc] = max(lazy_tree[lc], lazy_tree[id]);
        lazy_tree[rc] = max(lazy_tree[rc], lazy_tree[id]);

        // Đặt lại giá trị lazy của nút hiện tại
        lazy_tree[id] = -INF;
    }
}

// Xây dựng cây phân đoạn
void build_tree(int id, int l, int r) {
    lazy_tree[id] = -INF;
    min_h_tree[id] = INF; // Khởi tạo min là vô cực
    max_diff_tree[id] = -INF; // Khởi tạo max_diff là âm vô cực
    if (l == r) return;
    int mid = (l + r) >> 1;
    build_tree(id << 1, l, mid);
    build_tree(id << 1 | 1, mid + 1, r);
}

// Cập nhật điểm: thay đổi giá trị chiều cao của một item tại vị trí `pos`
void update_point_height(int id, int l, int r, int pos, ll value) {
    push_down(id);
    if (l == r) {
        min_h_tree[id] = value;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        push_down(id << 1 | 1); // Đẩy lazy của nút anh em trước khi cập nhật
        update_point_height(id << 1, l, mid, pos, value);
    } else {
        push_down(id << 1); // Đẩy lazy của nút anh em
        update_point_height(id << 1 | 1, mid + 1, r, pos, value);
    }
    min_h_tree[id] = min(min_h_tree[id << 1], min_h_tree[id << 1 | 1]);
    max_diff_tree[id] = max(max_diff_tree[id << 1], max_diff_tree[id << 1 | 1]);
}

// Cập nhật đoạn: áp dụng giá trị h_j (val) cho tất cả các item i trong đoạn [x, y]
void update_range_lazy(int id, int l, int r, int x, int y, ll val) {
    push_down(id);
    if (y < l || r < x) return;
    if (x <= l && r <= y) {
        lazy_tree[id] = max(lazy_tree[id], val);
        push_down(id);
        return;
    }
    int mid = (l + r) >> 1;
    update_range_lazy(id << 1, l, mid, x, y, val);
    update_range_lazy(id << 1 | 1, mid + 1, r, x, y, val);
    min_h_tree[id] = min(min_h_tree[id << 1], min_h_tree[id << 1 | 1]);
    max_diff_tree[id] = max(max_diff_tree[id << 1], max_diff_tree[id << 1 | 1]);
}

// Truy vấn đoạn: lấy giá trị max_diff_tree lớn nhất trong đoạn [x, y]
ll query_max_diff(int id, int l, int r, int x, int y) {
    push_down(id);
    if (y < l || r < x) return -INF;
    if (x <= l && r <= y) return max_diff_tree[id];
    int mid = (l + r) >> 1;
    return max(
        query_max_diff(id << 1, l, mid, x, y),
        query_max_diff(id << 1 | 1, mid + 1, r, x, y)
    );
}

// Hàm chính thực hiện thuật toán Sweep-line
void run_sweep_line() {
    build_tree(1, 1, num_items);
    int sweep_pos = 0;
    for (int i = 1; i <= num_queries; i++) {
        int L = queries[i].l, R = queries[i].r, idx = queries[i].id;
        
        // Di chuyển đường quét đến điểm cuối `R` của truy vấn hiện tại
        while (sweep_pos < R) {
            sweep_pos++;
            
            // Xử lý các item bắt đầu có hiệu lực tại sweep_pos
            for (int p : start_events[sweep_pos]) {
                update_point_height(1, 1, num_items, p, items[p].height);
            }
            
            // Xử lý các item kết thúc hiệu lực tại sweep_pos bằng cách đặt chiều cao của chúng là vô cực
            for (int p : end_events[sweep_pos]) {
                update_point_height(1, 1, num_items, p, INF);
            }
            
            // Item tại `sweep_pos` giờ là `j`. Tìm các `i` thỏa mãn `l_j <= j-i <= r_j`
            // Tức là `j - r_j <= i <= j - l_j`
            ll lo = max(1LL, (ll)sweep_pos - items[sweep_pos].max_dist);
            ll hi = max(1LL, (ll)sweep_pos - items[sweep_pos].min_dist);
            
            if (lo <= hi) {
                // Áp dụng chiều cao của item j (items[sweep_pos].height) cho tất cả các i trong đoạn [lo, hi]
                update_range_lazy(1, 1, num_items, lo, hi, items[sweep_pos].height);
            }
        }
        
        // Trả lời truy vấn cho đoạn [L, R]
        results[idx] = max(results[idx], query_max_diff(1, 1, num_items, L, R));
    }
}

signed main() {
    // Tăng tốc độ nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> num_items;
    for (int i = 1; i <= num_items; i++) {
        cin >> items[i].height >> items[i].min_dist >> items[i].max_dist;
        if (i + items[i].min_dist <= num_items) {
            start_events[i + items[i].min_dist].push_back(i);
        }
        if (i + items[i].max_dist + 1 <= num_items) {
            end_events[i + items[i].max_dist + 1].push_back(i);
        }
    }

    cin >> num_queries;
    for (int i = 1; i <= num_queries; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    
    sort(queries + 1, queries + 1 + num_queries, compare_queries);
    for (int i = 1; i <= num_queries; i++) results[i] = -1;

    // --- Lần chạy thứ nhất: Tìm max(h_j - h_i) ---
    run_sweep_line();

    // --- Chuẩn bị cho lần chạy thứ hai ---
    // Để tìm max(h_i - h_j), ta biến đổi h' = C - h và tìm max(h'_j - h'_i)
    // max(h'_j - h'_i) = max((C - h_j) - (C - h_i)) = max(h_i - h_j)
    for (int i = 1; i <= num_items; i++) {
        items[i].height = INF - items[i].height;
        // Xóa các vector sự kiện để chuẩn bị cho lần chạy thứ hai
        start_events[i].clear();
        end_events[i].clear();
    }
    // Cần thêm vector `end_events` cho vị trí > num_items
    for (int i = num_items + 1; i < MAX_N; ++i) end_events[i].clear();


    // Tạo lại các sự kiện với chiều cao đã biến đổi
    for (int i = 1; i <= num_items; i++) {
        if (i + items[i].min_dist <= num_items) {
            start_events[i + items[i].min_dist].push_back(i);
        }
        if (i + items[i].max_dist + 1 <= num_items) {
            end_events[i + items[i].max_dist + 1].push_back(i);
        }
    }

    // --- Lần chạy thứ hai: Tìm max(h_i - h_j) ---
    run_sweep_line();

    // In kết quả cuối cùng
    for (int i = 1; i <= num_queries; i++) {
        cout << results[i] << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65