제출 #1343061

#제출 시각아이디문제언어결과실행 시간메모리
1343061minhtienGlobal Warming (CEOI18_glo)C++20
15 / 100
396 ms24176 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=7e5+6;
int n,x;
int a[N];
ll dp[N],dp1[N];
vector<ll>v;
map<ll,int>v1;
int tree[4*N];
ll tong=0;
int k=1;
void update(int id,int l,int r,int i,int val){
    if(i>r || i<l) return ;
    if(l==r){
        tree[id]=max(tree[id],val);
        return ;
    }
    int m=(l+r)/2;
    update(id*2,l,m,i,val);
    update(id*2+1,m+1,r,i,val);
    tree[id]=max(tree[id*2],tree[id*2+1]);
}
int get(int id,int l,int r,int x,int y){
    if(r<x || l>y) return 0;
    if(l>=x && r<=y) return tree[id];
    int m=(l+r)/2;
    return max(get(id*2,l,m,x,y),get(id*2+1,m+1,r,x,y));
}
void f(){
    sort(v.begin(),v.end());
    v1[v[0]]=k;
    for(int i=1;i<v.size();i++){
        if(v[i]!=v[i-1]) k++;
        v1[v[i]]=k;
    }
}
int main()
{
    cin >>n >>x;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
        ll sum=a[i];
        ll sum1=a[i]-x;
        ll sum2=a[i]+x;
        v.push_back(sum);
        v.push_back(sum1);
        v.push_back(sum2);
    }
    f();
    for(int i=1;i<=n;i++){
        dp[i]=1;
        if(a[i]>a[i-1]) dp[i]=dp[i-1]+1;
    }
    for(int j=n;j>=1;j--){
        ll sum=a[j]-x;
        ll maxi=get(1,1,k,v1[sum]+1,k);
        ll maxi1=get(1,1,k,v1[a[j]]+1,k);
        tong=max(tong,dp[j]+maxi);
        update(1,1,k,v1[a[j]],maxi1+1);
    }
    cout << tong;
    return 0;
}
#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...