Submission #989757

#TimeUsernameProblemLanguageResultExecution timeMemory
989757parlimoosGlobal Warming (CEOI18_glo)C++14
100 / 100
305 ms12668 KiB
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , x;
vector<int> cmp , a;
int seginf[800001][2] , seg[800001] , is[200000];
int dp[200000][2];
int o = 0;

void cmpInt(){
    sort(cmp.bg() , cmp.end());
    cmp.resize(int(unique(cmp.bg() , cmp.end()) - cmp.bg()));
    for(int &el : a) el = int(lb(cmp.bg() , cmp.end() , el) - cmp.bg());
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r , seg[i] = 0;
    if(l == r) is[l] = i;
    else{
        int c = (l + r - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
    }
}
void updSeg(int i , int val){
    while(i >= 1) seg[i] = max(seg[i] , val) , i >>= 1;
}
int getSeg(int l , int r , int i){
    if(r < l) return 0;
    if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i];
    if(seginf[i][1] >= l and seginf[i][0] <= r) return max(getSeg(l , r , i << 1) , getSeg(l , r , (i << 1) | 1));
    return 0;
}
void f(){
    buildSeg();
    for(int i = 0 ; i < n ; i++){
        dp[i][0] = getSeg(0 , a[i] - 1 , 1) + 1;
        updSeg(is[a[i]] , dp[i][0]);
    }
    buildSeg();
    for(int i = n - 1 ; i >= 0 ; i--){
        dp[i][1] = getSeg(a[i] + 1 , n - 1 , 1) + 1;
        updSeg(is[a[i]] , dp[i][1]);
    }
    buildSeg();
    for(int i = 0 ; i < n ; i++){
        int inx = int(lb(cmp.bg() , cmp.end() , cmp[a[i]] + x) - cmp.bg());
        o = max(o , getSeg(0 , inx - 1 , 1) + dp[i][1]);
        updSeg(is[a[i]] , dp[i][0]);
    }
    buildSeg();
    for(int i = n - 1 ; i >= 0 ; i--){
        int inx = int(ub(cmp.bg() , cmp.end() , cmp[a[i]] - x) - cmp.bg());
        o = max(o , getSeg(inx , n - 1 , 1) + dp[i][0]);
        // if(o == 6) cout << i << "!!\n";
        updSeg(is[a[i]] , dp[i][1]);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> x;
    for(int i = 0 ; i < n ; i++){
        cmp.pb(0);
        cin >> cmp.back();
        a.pb(cmp.back());
    }
    cmpInt() , f();
    cout << o;
}
#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...