Submission #1186973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186973		Born_To_Laugh	Global Warming (CEOI18_glo)	C++17	100 / 100	297 ms	28580 KiB

glo

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(sth) sth.begin(), sth.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

#define int ll
struct Segment_Tree {
    int n;
    vector<int> st;
    Segment_Tree(int _n): n(_n), st(4*n, 0) {}
    void update(int id, int l, int r, int pos, int val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id] = max(st[id], val);
            return;
        }
        int mid = (l + r) >> 1;
        update(id<<1, l, mid, pos, val);
        update(id<<1|1, mid+1, r, pos, val);
        st[id] = max(st[id<<1], st[id<<1|1]);
    }
    int get(int id, int l, int r, int u, int v) {
        if (r < u || l > v) return -INF;
        if (u <= l && r <= v) return st[id];
        int mid = (l + r) >> 1;
        return max(get(id<<1, l, mid, u, v),
                   get(id<<1|1, mid+1, r, u, v));
    }
    void update(int pos, int val) { update(1,1,n,pos,val); }
    int get(int l, int r) { return get(1,1,n,l,r); }
};

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n+1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> temp;
    for (int i = 1; i <= n; ++i) {
        temp.push_back(a[i] + 1);
        temp.push_back(a[i] + 1 - x);
        temp.push_back(a[i]);
    }
    temp.push_back(INF);
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    auto get_pos = [&](int v) {
        return int(upper_bound(temp.begin(), temp.end(), v) - temp.begin()) + 1;
    };

    vector<int> dp;
    vector<int> lis(n+10, 0);

    for (int i = 1; i <= n; ++i) {
        int pos = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
        if (pos == (int)dp.size()) dp.push_back(a[i]);
        else dp[pos] = a[i];
        lis[i] = pos + 1;
    }
    Segment_Tree seg(temp.size() + 10);
    vector<int> suff(n+10);

    int INFpos = get_pos(INF);

    for (int i = n; i >= 1; --i) {
        suff[i] = seg.get(get_pos(a[i] + 1 - x), INFpos);
        seg.update(get_pos(a[i]), seg.get(get_pos(a[i] + 1), INFpos) + 1);
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, lis[i] + suff[i]);
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• 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