Submission #1274966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274966		rana_azka	Global Warming (CEOI18_glo)	C++20	28 / 100	2095 ms	5096 KiB

glo

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

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5;

int n, m;
int arr[MAXN+5];
int dp_pref[MAXN+5];
int dp_suff[MAXN+5];

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> arr[i];

    vector<int> v;
    v.push_back(-INF);
    int sz = 0;
    for(int i = 1; i <= n; i++){
        int idx = 0;
        int left = 0, right = sz;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(v[mid] < arr[i]){
                idx = mid + 1;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        
        dp_pref[i] = idx;
        if(idx <= sz){
            v[idx] = min(arr[i], v[idx]);
        }else{
            v.push_back(arr[i]);
            sz++;
        }
    }
    
    v.clear();
    v.push_back(INF);
    sz = 0;
    for(int i = n; i >= 1; i--){
        int idx = 0;
        int left = 0, right = sz;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(v[mid] > arr[i]){
                idx = mid + 1;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        
        dp_suff[i] = idx;
        if(idx <= sz){
            v[idx] = max(arr[i], v[idx]);
        }else{
            v.push_back(arr[i]);
            sz++;
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(arr[i] - arr[j] < m) ans = max(dp_pref[i] + dp_suff[j], ans);
        }
    }

    cout << ans << endl;

    // for(int i = 1; i <= n; i++) cerr << dp_pref[i] << ' ';
    // cerr << endl;
    // for(int i = 1; i <= n; i++) cerr << dp_suff[i] << ' ';
    // cerr << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        solve();
    }

    return 0;
}

/*
TEST CASE

8 10
7 3 5 12 2 7 3 4
=> 5
*/

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