Submission #1241974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241974		orzorzorz	Global Warming (CEOI18_glo)	C++20	100 / 100	339 ms	38804 KiB

glo

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

using namespace std;

const int INF = 2e9;

// 計算 LIS 的輔助函式
// 傳入一個數組，返回一個向量，其中 result[i] 是以原數組第 i 個元素結尾的 LIS 長度
vector<int> get_lis_lengths(const vector<int>& arr) {
    if (arr.empty()) {
        return {};
    }
    int n = arr.size();
    vector<int> result(n);
    vector<int> dp; // dp[i] 存儲長度為 i+1 的 LIS 的最小結尾元素

    for (int i = 0; i < n; ++i) {
        auto it = lower_bound(dp.begin(), dp.end(), arr[i]);
        result[i] = (it - dp.begin()) + 1;
        if (it == dp.end()) {
            dp.push_back(arr[i]);
        } else {
            *it = arr[i];
        }
    }
    return result;
}

// 線段樹結構，用於區間最大值查詢
vector<int> seg_tree;
int seg_tree_size;

void update_seg_tree(int idx, int val, int x, int lx, int rx) {
    if (rx - lx == 1) {
        seg_tree[x] = max(seg_tree[x], val);
        return;
    }
    int m = (lx + rx) / 2;
    if (idx < m) {
        update_seg_tree(idx, val, 2 * x + 1, lx, m);
    } else {
        update_seg_tree(idx, val, 2 * x + 2, m, rx);
    }
    seg_tree[x] = max(seg_tree[2 * x + 1], seg_tree[2 * x + 2]);
}

int query_seg_tree(int l, int r, int x, int lx, int rx) {
    if (lx >= r || l >= rx) return 0;
    if (lx >= l && rx <= r) return seg_tree[x];
    int m = (lx + rx) / 2;
    int s1 = query_seg_tree(l, r, 2 * x + 1, lx, m);
    int s2 = query_seg_tree(l, r, 2 * x + 2, m, rx);
    return max(s1, s2);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long x;
    cin >> n >> x;

    vector<int> t(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }

    // 1. 座標離散化
    vector<long long> discrete_vals;
    for (int val : t) {
        discrete_vals.push_back(val);
        discrete_vals.push_back((long long)val + x);
    }
    sort(discrete_vals.begin(), discrete_vals.end());
    discrete_vals.erase(unique(discrete_vals.begin(), discrete_vals.end()), discrete_vals.end());

    map<long long, int> val_to_idx;
    for (int i = 0; i < discrete_vals.size(); ++i) {
        val_to_idx[discrete_vals[i]] = i;
    }

    // 2. 預處理 pre_lis 和 suf_lis
    vector<int> pre_lis = get_lis_lengths(t);

    vector<int> t_rev(n);
    for (int i = 0; i < n; ++i) {
        t_rev[i] = -t[n - 1 - i];
    }
    vector<int> suf_lis_rev = get_lis_lengths(t_rev);
    vector<int> suf_lis(n);
    for (int i = 0; i < n; ++i) {
        suf_lis[i] = suf_lis_rev[n - 1 - i];
    }

    // 3. 初始化答案
    int max_len = 0;
    for (int len : pre_lis) {
        max_len = max(max_len, len);
    }

    // 4. 初始化線段樹
    seg_tree_size = discrete_vals.size();
    seg_tree.assign(4 * seg_tree_size, 0);

    // 5. 主迴圈，尋找最佳拼接
    for (int j = 0; j < n; ++j) {
        // 查詢滿足 t_i < t_j + x 的所有 i < j 中，pre_lis[i] 的最大值
        long long target_val = (long long)t[j] + x;
        auto it = lower_bound(discrete_vals.begin(), discrete_vals.end(), target_val);
        
        int query_range_end = it - discrete_vals.begin();
        
        int max_pre = 0;
        if (query_range_end > 0) {
            max_pre = query_seg_tree(0, query_range_end, 0, 0, seg_tree_size);
        }

        if (max_pre > 0) {
            max_len = max(max_len, max_pre + suf_lis[j]);
        }

        // 將 pre_lis[j] 更新到線段樹中
        int update_idx = val_to_idx[t[j]];
        update_seg_tree(update_idx, pre_lis[j], 0, 0, seg_tree_size);
    }

    cout << max_len << endl;

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25