Submission #1207074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207074		mopsyarka	Global Warming (CEOI18_glo)	C++20	100 / 100	38 ms	2716 KiB

glo

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define f first
#define s second

#define sz(x) (ll)(x.size())

#define vec vector
#define pb push_back
#define all(x) x.begin(), x.end()

#define debug(x) cerr << (#x) << " = " << (x) << endl

ll pw (int a) {
    return 1ll << a;
}

using pii = pair < int, int >;
using pll = pair < ll, ll >;

const int mod = 998244353;
const int N = 2e5 + 5;
const ll OO = 2e9;
const ld eps = 1e-10;

template<typename T>
bool umn (T &fi, T se) { return fi > se ? (fi = se, 1) : 0; }

template<typename T>
bool umx (T &fi, T se) { return fi < se ? (fi = se, 1) : 0; }

int a[N], res[N];

void slv () {
//    freopen("cowjog.in", "r", stdin);
//    freopen("cowjog.out", "w", stdout);

    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector < int > dp(n + 1, OO);
    dp[0] = -OO;

    for (int i = n - 1; i >= 0; --i) {

        int p = lower_bound(all(dp), -a[i]) - dp.begin();
        res[i] = p;
        dp[p] = -a[i];
    }

    int ans = 0;
    fill(all(dp), OO);
    dp[0] = -OO;
    for (int i = 0; i < n; ++i) {

        int x = a[i] + d;
        int pi = lower_bound(all(dp), x) - dp.begin() - 1;
        ans = max(ans, pi + res[i]);

        pi = lower_bound(all(dp), a[i]) - dp.begin();
        dp[pi] = a[i];

    }
    cout << ans;

}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
//    cin >> test;
    while (test--) {
        slv();
        cout << "\n";
    }
}

///    Skyline Ryodan

///Да это же Midix!
///Trippy, cooking that shit up again

///Мой quinque это Desolator, да, я Сузуя Джузо
///Видел так много смертей близких, затупились все чувства
///Читаю словно на спидах, бля, я Ликаном покусан
///Какой паук тебе, пацан? Ты — человеческий мусор
///Я ебанутый на голову, скорость ударила в голову
///Будешь пиздеть — с корнями вырву твою голову
///В моей системе веет од, паук не знает слова «голод»
///Оставлю пару пулевых на теле, сука, мне не нужен повод

///Это Редан, здесь пауки, в Sky'е летим прямо в ад
///Если ты прыгнул в этот сквад, то точно нет пути назад
///Да твои парни — это крысы, будто Хилл Зодиак
///И моя клика вырубает вас за пару атак!

///Юзаю drug, я перебил стак, ты знаешь как мне похуй на luck
///На линзах мрак, нет, это не знак, я знаю: ты слаб, ты ёбаный раб
///Продал души, я бессмертен, кровью подписан контракт
///И под звуки Реквиема я танцую на костях!

///Всё, что держу в своих руках — это я сделал сам
///Я не нуждаюсь в представлении, Jinada скам
///Здесь пауки, мы поколение, со мной Редан
///Skyline узнает где ты, сука, нам не нужен скан (Ра)
///Пауков целая стая, психопаты за рулём
///За штурвал hikikomori, левый глаз залит огнём
///Весь салон пропитан болью и я роллю прямо в нём
///И под капотом триста двадцать, насладись последним днём, а

///Это mindset от Бога
///Моё дыхание грома
///Мои глаза видят пустых — это глаукома
///Это mindset от Бога-Бога
///Моё дыхание грома
///Мои гла—, мои гла— видят пустых, глаук—

///Проклятый ублюдок, на мне метка паука
///Двенадцать лап на моей шее, подо мной крови река
///Полный бак залитый в Sky'е, по мне плачут небеса
///Клеймо четвёрки на спине и труппа, скрытая в тенях

///Я ебанутый на голову, скорость ударила в голову
///Будешь пиздеть — с корнями вырву твою голову
///Я ебанутый на голову, скорость ударила в голову
///Будешь пиздеть — с корнями вырву твою голову
///Аллё, shadow-shadow, блядь, сук—, идите нахуй
///Отпустите меня домой, ха-ха-ха

• 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