Submission #1131658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131658		jadai007	Global Warming (CEOI18_glo)	C++17	10 / 100	116 ms	6716 KiB

glo

/*
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;
}

• Subtask 1: 0 / 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