제출 #1276185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276185		nanaseyuzuki	Global Warming (CEOI18_glo)	C++20	0 / 100	101 ms	3620 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, m, x, a[mn], lis[mn];

int bit[mn];

void add_pre(int u, int val){
    while(u <= m){
        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 <= m){
        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());
    m = comp.size();

    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();
        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();
}

• 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