Submission #1161547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161547		PikachudoraEHE	Global Warming (CEOI18_glo)	C++20	0 / 100	30 ms	3012 KiB

glo

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+5;
vector<int>a(N),mem,mem2;
vector<int>memreal(N);
map<int,int>m;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,x;cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(mem.empty()){
            mem.push_back(a[i]-x);
            memreal[i]=1;
            continue;
        }
        auto itr = lower_bound(mem.begin(),mem.end(),a[i]-x);
        if(itr==mem.end()){
            mem.push_back(a[i]-x);
            memreal[i]=mem.size();
        }
        else{
            *(itr)=a[i]-x;
            memreal[i]=itr-mem.begin()+1;
        }
    }
    int ans = mem.size();
    for(int i=n;i>=1;i--){
        if(mem2.empty()){
            mem2.push_back(-a[i]);
        }
        else {
            auto itr2 = lower_bound(mem2.begin(),mem2.end(),-memreal[i]);
            int idx = itr2-mem2.begin();
            ans=max(ans,idx+memreal[i]);
            auto itr = lower_bound(mem2.begin(),mem2.end(),-a[i]);
            if(itr==mem2.end()){
                mem2.push_back(-a[i]);
            }
            else{
                *(itr)=-a[i];
            }
        }
    }
    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: 0 / 17
• Subtask 7: 0 / 25