Submission #1131658

#TimeUsernameProblemLanguageResultExecution timeMemory
1131658jadai007Global Warming (CEOI18_glo)C++17
10 / 100
116 ms6716 KiB
/*
Author : detective conan
problem : CEOI18_Global Warming
*/
#include<bits/stdc++.h>
#define int long long

using namespace std;

const bool HAVE_TESTCASE = false;

int fw[200200], n, arr[200200], x, ans, pre[200200];
vector<int> vc;

void upd(int idx, int val){
    for(; idx <= n; idx += (idx&-idx)) fw[idx] = max(fw[idx], val);
}

int qry(int idx, int mx = -1){
    for(; idx > 0; idx -= (idx&-idx)) mx = max(mx, fw[idx]);
    return mx;
}

void solve(){
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) cin >> arr[i], vc.push_back(arr[i]);
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    for(int i = 1; i <= n; ++i){
        int idx = lower_bound(vc.begin(), vc.end(), arr[i]) - vc.begin();
        idx--;
        if(idx >= 0) pre[i] = qry(idx + 1) + 1;
        else pre[i] = 1;
        ans = max(ans, pre[i]);
        upd(idx + 2, pre[i]);
    }
    memset(fw, 0, sizeof(fw));
    vc.clear();
    for(int i = 1; i <= n; ++i) vc.push_back(-arr[i]);
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    for(int i = n; i > 0; --i){
        int idx = lower_bound(vc.begin(), vc.end(), -arr[i] + x) - vc.begin();
        idx--;
        if(idx >= 0) ans = max(ans, pre[i] + qry(idx + 1));
        idx = lower_bound(vc.begin(), vc.end(), -arr[i]) - vc.begin();
        upd(idx + 2, qry(idx + 1) + 1);
    }
    cout << ans << '\n';
}

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    if(HAVE_TESTCASE) cin >> t;
    while(t--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...