Submission #1125131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125131		ardadut	Global Warming (CEOI18_glo)	C++20	100 / 100	51 ms	5824 KiB

glo

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

inline void solve(){

    ll n,x,ans = 0;
    cin >> n >> x;
    vector<ll> temps(n);
    vector<ll> prefix_lis(n);

    for(ll i = 0 ; i < n ; i++) cin >> temps[i];

    vector<ll> lis;
    for(ll i = 0 ; i < n ; i++){
        ll j = lower_bound(lis.begin(),lis.end(),temps[i]) - lis.begin();
        if(j == lis.size()) lis.pb(temps[i]);
        else lis[j] = temps[i];
        prefix_lis[i] = j+1;
        ans = max(ans,prefix_lis[i]);
    }

    vector<ll> lis2;
    for(ll i = n-1 ; i >= 0 ; i--){
        ll pos = lower_bound(lis2.begin(),lis2.end(),-temps[i]+x) - lis2.begin();
        ans = max(ans,prefix_lis[i] + pos);

        ll j = lower_bound(lis2.begin(),lis2.end(),-temps[i]) - lis2.begin();
        if(j == lis2.size()) lis2.pb(-temps[i]);
        else lis2[j] = -temps[i];
    }

    cout << ans << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

• 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