Submission #953815

#	Time	Username	Problem	Language	Result	Execution time	Memory
953815		MuntherCarrot	Global Warming (CEOI18_glo)	C++14	100 / 100	159 ms	10376 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
const int MOD = 1e9 + 7;

template<typename T>
struct segTree{
    vector<T> t;
    int N;
    segTree(int n) : N(1){
        while(N < n) N <<= 1;
        t.resize(N << 1);
    }
    segTree(const vector<T> &vec) : segTree(vec.size()){
        for(int i = 0; i < (int)vec.size(); i++){
            t[i + N] = vec[i];
        }
        for(int i = N - 1; i > 0; i--){
            t[i] = max(t[i << 1], t[i << 1 | 1]);
        }
    }
    void upd(int i, T val){
        assert(i >= 0 && i < N);
        i += N;
        t[i] = t[i] + val;
        while(i >>= 1){
            t[i] = max(t[i << 1], t[i << 1 | 1]);
        }
    }
    T clc(int l, int r, int i, int from, int to){
        if(from > r || to < l){
            return T();
        }
        if(from >= l && to <= r){
            return t[i];
        }
        int mid = (from + to) >> 1;
        return max(clc(l, r, i << 1, from, mid), clc(l, r, i << 1 | 1, mid + 1, to));
    }
    T clc(int l, int r){
        assert(l >= 0 && l <= r && r < N);
        return clc(l, r, 1, 0, N - 1);
    }
};

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, x;
    cin >> n >> x;
    int a[n];
    for(int &i : a){
        cin >> i;
    }
    int l[n], r[n];
    int dp[n];
    memset(dp, INF, sizeof dp);
    for(int i = 0; i < n; i++){
        int x = lower_bound(dp, dp + n, a[i]) - dp;
        l[i] = x + 1;
        dp[x] = a[i];
    }
    memset(dp, INF, sizeof dp);
    for(int i = n - 1; i >= 0; i--){
        int x = lower_bound(dp, dp + n, -a[i]) - dp;
        r[i] = x + 1;
        dp[x] = -a[i];
    }
    vector<int> vec(n);
    iota(all(vec), 0);
    sort(all(vec), [&](int x, int y){
        return a[x] > a[y];
    });
    int ans = 0;
    segTree<int> L(n), R(n);
    for(int i = 0, j = 0; i < n; i++){
        int idx = vec[i];
        while(j < i && a[vec[j]] - a[idx] >= x){
            L.upd(vec[j], -l[vec[j]]);
            R.upd(vec[j], -r[vec[j]]);
            j++;
        }
        ans = max(ans, l[idx] + R.clc(idx, n - 1));
        ans = max(ans, L.clc(0, idx) + r[idx]);
        L.upd(idx, l[idx]);
        R.upd(idx, r[idx]);
    }
    cout << ans << endl;
    return 0;
}
// by me

• 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