Submission #1165710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165710		altern23	Global Warming (CEOI18_glo)	C++20	15 / 100	348 ms	3888 KiB

glo

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, x; cin >> n >> x;
        vector<ll> a(n + 5);
        for(int i = 1; i <= n; i++) cin >> a[i];

        auto f = [&](ll idx){
            vector<ll> cur;
            for(int j = 1; j <= n; j++){
                ll val = a[j] - (idx >= j ? x : 0);
                if(cur.empty() || cur.back() < val){
                    cur.push_back(val);
                }
                else{
                    ll pt = lower_bound(cur.begin(), cur.end(), val) - cur.begin();
                    if(pt != cur.size()) cur[pt] = val;
                }
            }
            return (ll)cur.size();
        };
        
        ll lf = 0, rg = n;
        for(;rg - lf > 1;){
            ll mid = (lf + rg) / 2;
            if(f(mid) > f(mid + 1)){
                rg = mid;
            }
            else lf = mid;
        }

        cout << f(lf + 1) << "\n";
    }   
}

/*

*/ 

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