Submission #1157239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157239		ocasu	Global Warming (CEOI18_glo)	C++20	100 / 100	165 ms	14512 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf=1e12;

signed main(){
    int n,x; cin>>n>>x;
    vector<int> a(n,0);
    for (int i=0; i<n; i++) cin>>a[i];
    vector<int> pre(n,1), suf(n,1);
    vector<int> left(n,-1), right(n,-1);
    int ans=0;
    {
        set<pair<int,int>> s;
        for (int i=0; i<n; i++){
            if (!s.empty()){
                auto itr=s.lower_bound({a[i],-inf});
                if (itr != s.begin()) {
                    itr--;
                    pre[i] = (*itr).second + 1;
                }
                itr = s.lower_bound({a[i]+x, -inf});
                if (itr != s.begin()){
                    itr--;
                    left[i] = (*itr).second;
                }
            }
            while (true){
                auto itr=s.lower_bound({a[i],-inf});
                if (!s.empty() and itr!=s.end() and (*itr).second <= pre[i]){
                    s.erase(itr);
                } else{
                    break;
                }
            }
            ans=max(ans, pre[i]);
            s.insert({a[i],pre[i]});
        }
    }

    {
        set<pair<int,int>> s;
        for (int i=n-1; i>=0; i--){
            if (!s.empty()){
                auto itr=s.upper_bound({a[i],inf});
                if (itr != s.end()) {
                    suf[i] = (*itr).second + 1;
                }
                itr = s.upper_bound({a[i]-x, inf});
                if (itr != s.end()){
                    right[i] = (*itr).second;
                }
            }
            while (true){
                auto itr=s.lower_bound({a[i],-inf});
                if (!s.empty() and itr!=s.begin() and (*(--itr)).second <= suf[i]){
                    s.erase(itr);
                } else{
                    break;
                }
            }
            s.insert({a[i],suf[i]});
        }
    }
    
    for (int i=0; i<n-1; i++){
        if (right[i]!=-1){
            ans=max(ans, left[i] + suf[i]);
        }
    }
    for (int i=1; i<n-1; i++){
        if (left[i] !=-1){
            ans=max(ans, pre[i] + right[i]);
        }
    }
    //for (int i=0; i<n; i++){
    //    cout<<right[i]<<' ';
    //}
    //cout<<'\n';
    cout<<ans<<'\n';



}

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