Submission #1187258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187258		dirtycodehehe	Global Warming (CEOI18_glo)	C++20	17 / 100	69 ms	4544 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,x;
    cin>>n>>x;
    vector<int> a(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    vector<int> v;
    vector<int> pre(n);
    for(int i=0;i<n;++i){
        if(v.empty()||a[i]>v.back()){
            v.push_back(a[i]);
            pre[i]=v.size();
        } else {
            int pos=lower_bound(v.begin(),v.end(),a[i])-v.begin();
            pre[i]=pos+1;
            v[pos]=a[i];
        }
    }
    v.clear();
    int ans=0;
    // giảm dần dài nhất
    for(int i=n-1;i>=0;--i){
        if(v.empty()||v.back()>a[i]){
            v.push_back(a[i]);
        } else {
            *--upper_bound(v.rbegin(),v.rend(),a[i])=a[i];
        }
        if(i==0){
            ans=max(ans,(int)v.size());
        } else {
            ans=max(ans,pre[i-1]+(int)v.size()-(upper_bound(v.rbegin(),v.rend(),a[i]-x)-v.rbegin()));
        }
    }
    cout<<ans;
    return 0;
}

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