Submission #1343071

#TimeUsernameProblemLanguageResultExecution timeMemory
1343071minhtienGlobal Warming (CEOI18_glo)C++20
17 / 100
550 ms47852 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e6+6;
const int inf=1e9+7;
int n,x;
int a[N];
ll dp[N],dp1[N];
vector<ll>v;
map<ll,int>v1;
int tree[4*N];
vector<int>v2;
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();
    v2.push_back(-inf);
    for(int i=1;i<=n;i++){
        int t=lower_bound(v2.begin(),v2.end(),a[i])-v2.begin();
        if(t==v2.size()){
            v2.push_back(a[i]);
        }
        else{
            v2[t]=a[i];
        }
//        cout << i << " " << t << " " << a[i] << " " << v2.size() << "\n";
        dp[i]=v2.size()-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...