제출 #1143636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143636		DON_F	Global Warming (CEOI18_glo)	C++20	100 / 100	42 ms	2756 KiB

glo

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 2e5 + 7, Mx = 1e9 + 9;
int n, x;
int a[N];
int ed[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> x;
    L(i, 0, n){
        cin >> a[i];
    }
    vi l;
    L(i, 0, n){
        auto it = upper_bound(all(l), a[i] + x - 1);
        if (!l.empty() && it != l.begin()){
            --it;
            ed[i] = it - l.begin() + 1;
        }
        it = lower_bound(all(l), a[i]);
        if (it == l.end()){
            l.pb(a[i]);
        }else{
            *it = a[i];
        }
    }
    deque<int> t;
    int ans = 0;
    R(i, n - 1, 0){
        int it = upper_bound(all(t), a[i]) - t.begin();
        if (it == 0){
            t.push_front(a[i]);
            ans = max(ans, ed[i] + sz(t));
        }else{
            t[--it] = a[i];
            ans = max(ans, ed[i] + sz(t) - it);
        }
    }
    cout << ans;
}

• 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