제출 #931290

#제출 시각아이디문제언어결과실행 시간메모리
931290AtabayRajabliGlobal Warming (CEOI18_glo)C++17
100 / 100
49 ms10372 KiB
#include <bits/stdc++.h>

// author : a1abay

#define pb          push_back
#define all(v)      v.begin(), v.end()
#define int         ll
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   (a*b / (__gcd(a, b)))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            1e18 + 7;
const int sz =              2e5 + 5;
using namespace             std;

int n, x;
int a[sz];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> x;
    for(int i = 0; i < n; i++)cin >> a[i];

    vector<int> dp(n + 5, inff);
    vector<int> l(n + 5, 0), r(n + 5, 0);
    for(int i = 0; i < n; i++)
    {
        int ind = lower_bound(all(dp), a[i]) - dp.begin();
        dp[ind] = a[i];
        l[i] = ind + 1;
    }

    int mx = 0;
    dp = vector<int>(n + 5, inff);
    for(int i = n - 1; i >= 0; i--)
    {
        int pos = lower_bound(all(dp), -(a[i] - x)) - dp.begin();
        int ind = lower_bound(all(dp), -a[i]) - dp.begin();
        dp[ind] = -a[i];
        mx = max(mx, l[i] + pos);
    }

    cout << mx;
}
#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...