제출 #1276183

#제출 시각아이디문제언어결과실행 시간메모리
1276183nanaseyuzukiGlobal Warming (CEOI18_glo)C++20
0 / 100
40 ms2124 KiB
#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 1e5 + 5, mod = 998244353, inf = 1e9;

int n, x, a[mn], lis[mn];

int bit[mn];

void add_pre(int u, int val){
    while(u <= n){
        bit[u] = max(bit[u], val);
        u += (u & -u);
    }
}

int get_pre(int u){
    int res = 0;
    while(u){
        res = max(res, bit[u]);
        u -= (u & -u);
    }
    return res;
}

void add(int u, int val){
    while(u){
        bit[u] = max(bit[u], val);
        u -= (u & -u);
    }
}

int get(int u){
    if(u == 0) return 0;
    int res = 0;
    while(u <= n){
        res = max(res, bit[u]);
        u += (u & -u);
    }
    return res;
}

void solve(){
    cin >> n >> x;
    vector <int> comp;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        comp.push_back(a[i]);
    }
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());

    for(int i = 1; i <= n; i++){
        auto it = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin() + 1;
        lis[i] = get_pre(it - 1) + 1;
        add_pre(it, lis[i]);
    }
    fill(bit, bit + mn, 0);

    int res = lis[n];
    for(int i = n; i >= 1; i--){
        auto it = upper_bound(comp.begin(), comp.end(), a[i] - x) - comp.begin() + 1;
        int cur = get(it);
        res = max(res, lis[i - 1] + cur);
        it = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin() + 1;
        int pre = get(it + 1); add(it, pre + 1);
    }
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...