Submission #1343517

#TimeUsernameProblemLanguageResultExecution timeMemory
1343517po_rag526Global Warming (CEOI18_glo)C++17
0 / 100
33 ms3528 KiB
#ifdef LOCAL
#include <C:\Users\onlin\Desktop\competitive_programming\codes\debug.hpp>
#else
    #define dbg(x) 
    #define dbgl(x) 
    #define dbgvec(v) 
    #define DBG_OF(i, v)
#endif
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(v) v.begin(),v.end()
bool testcases=0;
int dx[]={-1,1,-1,1,2,2,-2,-2};
int dy[]={-2,-2,+2,2,-1,1,-1,1};
const int MOD=1e9+7;
const int inf=1e12;
const int ranint=65729178;
const int mynum=21;
const int N=1e6;
const int siz=N+mynum;
const int tsiz=4*siz;
void solve(){
    int n,x;
    cin>>n>>x;
    int v[n+1];
    for(int i=1;i<=n;i++)cin>>v[i];
    int pref[n+1];
    int ans=-1;
    vector<int> lis;
    for(int i=1;i<=n;i++){
        int num=v[i]-x;
        auto it=lower_bound(all(lis),num);
        if(it==lis.end()){
            lis.push_back(num);
        }
        else{
            lis[it-lis.begin()]=num;
        }
        pref[i]=it-lis.begin()+1;
        ans=max(ans,pref[i]);
    }
    lis.clear();
    for(int i=n;i>0;i--){
        int num=-v[i]+x;
        auto it=lower_bound(all(lis),num);
        if(it==lis.end()){
            lis.push_back(num);
        }
        else{
            lis[it-lis.begin()]=-v[i];
        }
        int temp=it-lis.begin()+1;
        ans=max(ans,pref[i]+temp);
    }
    cout<<ans<<endl;
}
signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1; 
    if(testcases)cin>>t;
    while(t--){
        solve();
    }
}
#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...