Submission #1276194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276194		nanaseyuzuki	Global Warming (CEOI18_glo)	C++20	0 / 100	120 ms	4492 KiB

glo

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x;
    if(!(cin >> n >> x)) return 0;
    vi a(n+1);
    vector<int> comp;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        comp.push_back(a[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int m = (int)comp.size();

    // forward LIS (prefix) using BIT for prefix-max
    vector<int> bit1(m+5, 0);
    auto add1 = [&](int pos, int val){
        while(pos <= m){
            bit1[pos] = max(bit1[pos], val);
            pos += pos & -pos;
        }
    };
    auto get1 = [&](int pos){
        int res = 0;
        while(pos > 0){
            res = max(res, bit1[pos]);
            pos -= pos & -pos;
        }
        return res;
    };

    vector<int> lis(n+1, 0);
    int res = 0;
    for(int i = 1; i <= n; ++i){
        int it = int(lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin()) + 1;
        lis[i] = get1(it - 1) + 1;
        res = max(res, lis[i]);
        add1(it, lis[i]);
    }

    // prepare BIT reversed for suffix queries: we want range max on [it..m],
    // map pos -> rpos = m - pos + 1 and use prefix-max on rpos
    vector<int> bit2(m+5, 0);
    auto add2 = [&](int pos, int val){
        while(pos <= m){
            bit2[pos] = max(bit2[pos], val);
            pos += pos & -pos;
        }
    };
    auto get2 = [&](int pos){
        int r = 0;
        while(pos > 0){
            r = max(r, bit2[pos]);
            pos -= pos & -pos;
        }
        return r;
    };

    // process from right to left
    for(int i = n; i >= 1; --i){
        // find first value >= a[i] + x  (NOT a[i] - x)
        int need_idx = int(lower_bound(comp.begin(), comp.end(), a[i] + x) - comp.begin()) + 1;
        int cur = 0;
        if(need_idx <= m){
            int rpos = m - need_idx + 1; // map suffix [need_idx..m] to prefix [1..rpos]
            cur = get2(rpos);
        }
        int leftLIS = (i > 1 ? lis[i-1] : 0); // guard for i==1
        res = max(res, leftLIS + cur);

        // now compute best suffix starting at i with values > a[i] (strictly larger)
        // find first value > a[i] => upper_bound
        int pos_gt = int(upper_bound(comp.begin(), comp.end(), a[i]) - comp.begin()) + 1;
        if(pos_gt <= m){
            int rpos_gt = m - pos_gt + 1;
            int bestAfter = get2(rpos_gt); // best starting from value > a[i]
            // update position of a[i] (rank)
            int rank_ai = int(lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin()) + 1;
            int upd_pos = m - rank_ai + 1;
            add2(upd_pos, bestAfter + 1);
        } else {
            // no greater value exists -> update a[i] with 1
            int rank_ai = int(lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin()) + 1;
            int upd_pos = m - rank_ai + 1;
            add2(upd_pos, 1);
        }
    }

    cout << res << '\n';
    return 0;
}

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