Submission #1276201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276201		nanaseyuzuki	Global Warming (CEOI18_glo)	C++20	100 / 100	102 ms	3696 KiB

glo

#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 = 2e5 + 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());
    int res = 0;
    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;
        res = max(res, lis[i]);
        add_pre(it, lis[i]);
    }
    fill(bit, bit + mn, 0);

    for(int i = n; i >= 1; i--){
        auto it = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin() + 1;
        int pre = get(it + 1); add(it, pre + 1);

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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) 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