Submission #1274992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274992		rana_azka	Global Warming (CEOI18_glo)	C++20	100 / 100	211 ms	25156 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;

#define md ((lf+rg)/2)
#define lc (pos*2)
#define rc (pos*2+1)

int n, m;
int arr[MAXN+5];
int dp_pref[MAXN+5];
int dp_suff[MAXN+5];
map<int, int> mp;
int ori[MAXN+5];
int segtree[4*MAXN+5];
int el;

void compress(){
    vector<int> v;
    for(int i = 1; i <= n; i++) v.push_back(arr[i]);
    sort(v.begin(), v.end());

    int idx = 1;
    for(int i = 0; i < n; i++){
        while(i > 0 && i < n && v[i] == v[i-1]) i++;
        
        mp[v[i]] = idx;
        ori[idx] = v[i];

        idx++;
    }
    el = idx - 1;

    // for(int i = 1; i <= el; i++) cerr << ori[i] << ' ';
    // cerr << endl;
}

int get_mp(int target){
    int ret = el;
    int left = 1, right = el;
    int mid;
    while(left <= right){
        mid = (left + right) / 2;
        if(ori[mid] >= target){
            ret = mid;
            right = mid - 1; 
        }else{
            left = mid + 1;
        }
    }

    return ret;
}

void update(int idx, int val, int lf, int rg, int pos){
    if(lf == rg){
        segtree[pos] = max(val, segtree[pos]);
        return ;
    }

    if(idx <= md) update(idx, val, lf, md, lc);
    else update(idx, val, md + 1, rg, rc);

    segtree[pos] = max(segtree[lc], segtree[rc]);
}

int query(int bor_lf, int bor_rg, int lf, int rg, int pos){
    if(rg < bor_lf || bor_rg < lf) return 0;
    if(bor_lf <= lf && rg <= bor_rg) return segtree[pos];

    return max(query(bor_lf, bor_rg, lf, md, lc), query(bor_lf, bor_rg, md + 1, rg, rc));
}

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

    compress();

    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 = n; i >= 1; i--){
        ans = max(dp_pref[i] + query(get_mp(arr[i] - m + 1), el, 1, el, 1), ans);
        // cerr << "res : " << dp_pref[i] << " + " << query(get_mp(arr[i] - m + 1), el, 1, el, 1) << endl;
        update(get_mp(arr[i]), dp_suff[i], 1, el, 1);
    }

    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: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25