Submission #920145

#	Time	Username	Problem	Language	Result	Execution time	Memory
920145		UmairAhmadMirza	Global Warming (CEOI18_glo)	C++17	62 / 100	80 ms	10972 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=200005;
int pre[N],suf[N];
int pre_val[N],suf_val[N];
void LIS(int arr[],int n){
    vector<int> v;
    v.push_back(arr[0]);
    pre[1]=1;
    pre_val[1]=arr[0];
    for(int i=1;i<n;i++){
        auto p=lower_bound(v.begin(),v.end(),arr[i]);
        if(p==v.end())
            v.push_back(arr[i]);
        else
            v[p-v.begin()]=arr[i];
        pre_val[i+1]=v.back();
        pre[i+1]=v.size();
    }
}
int ans=0;
void LIS_SUF(int arr[],int n,int x){
    vector<int> v;
    v.push_back(-arr[n-1]);
    for(int i=n-2;i>=0;i--){
        int pp=lower_bound(v.begin(),v.end(),-(pre_val[i+1]-x))-v.begin();
        // cout<<pre_val[i+1]<<' '<<pp<<endl;
        // for(auto j:v)
        //     cout<<j<<' ';
        // cout<<endl;
        ans=max(pre[i+1]+pp,ans);
        auto p=lower_bound(v.begin(),v.end(),-arr[i]);
        if(p==v.end())
            v.push_back(-arr[i]);
        else
            v[p-v.begin()]=-arr[i];
    }
    // cout<<endl;
}
signed main(){
    int n,x;
    cin>>n>>x;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    LIS(arr,n);
    if(x==0){
        cout<<pre[n]<<endl;
        return 0;
    }
    LIS_SUF(arr,n,x);
    cout<<max(ans,pre[n])<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25